LC145: Binary Tree Postorder Traversal

작성일

https://leetcode.com/problems/binary-tree-postorder-traversal/

  • stack으로 dfs 도는 문제이다.
  • 가장 중요한 point는 PRE, IN, POST state를 저장해야 한다는 점
  • 다른 중요한 점은 stack.top()을 고칠때는 래퍼런스를 받아와봐야 소용없고 직접 고쳐야 한다는 점이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    enum Status {PRE, IN, POST};
    struct Frame {
        TreeNode* node;
        Status status;
    };
    stack<Frame> st;
    vector<int> ans;
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return {};
        st.push({root, PRE});
        while(st.size()) {
            Frame cur = st.top();
            if(cur.status == PRE) {
                st.top().status = IN;
                if(cur.node->left) st.push({cur.node->left, PRE});
            }
            if(cur.status == IN) {
                st.top().status = POST;
                if(cur.node->right) st.push({cur.node->right, PRE});
            }
            if(cur.status == POST) {
                ans.push_back(cur.node->val);
                st.pop();
            }
        }
        return ans;
    }
};