Define a Node contain times of root pop


  • 0
    F
    class Solution {
    public:
        struct Node {//包含root结点出栈次数的结点
            TreeNode* node;
            int cnt;
            Node(TreeNode* x=NULL) : node(x), cnt(0) {}
        };
        
        vector<int> postorderTraversal(TreeNode* root){
            if(!root) return {};
            vector<int> res;
            stack<Node> s;
            Node cur(root);
            s.push(cur);
            
            while(!s.empty()){
                cur = s.top();
                s.pop();
                ++cur.cnt;
                if(cur.cnt == 3){//root结点第三次出栈,才能访问
                    res.push_back(cur.node->val);
                }
                if(cur.cnt == 2){//root结点第二次出栈,不能访问。要先访问右子树,所以还要将root结点入栈
                    s.push(cur);
                    if(cur.node->right) s.push(Node(cur.node->right));
                }
                if(cur.cnt == 1){
                    s.push(cur);//root结点第一次出栈,不能访问。要先访问左子树,所以还要将root结点入栈
                    if(cur.node->left) s.push(Node(cur.node->left));
                }
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.