My simple and very concise c++ solution with explanation (and real postorder)


  • 0
    S
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*>st;
        if(root) st.push(root);
        while(!st.empty()) {
            if(st.top()->left!=root && st.top()->right!=root) {
                while(auto x=st.top()) {
                    if(x->right) st.push(x->right);
                    if(x->left) st.push(x->left);
                    if(!x->right && !x->left) break;
                }
            }
            root=st.top();
            ret.push_back(root->val);
            st.pop();
        }
        return ret;
    }
    

    1.We can find the first node to visit by: go right only if we cannot go left and meanwhile push nodes to a stack; while we can go left, push it's right child first(*). If we find a leaf, that's it. That's what the inner while loop do.

    2.Now in the stack the older node is either the father or the right brother to the newer node. If father, next to visit. If right brother, repeat the first step.


Log in to reply
 

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