Think differently! Very easy solution.0 ms C++ method by modifying preorder


  • -1
    W

    What makes this problem harder than preorder and inorder problem is we must figure out the current Node we are visiting is the left child or right child.Think it in a differnent way!Postorder is left->right->root ,so we can traverse root->right->left,and then reverse it; It is simple to understand and we can just modify the preorder traverse:

    class Solution {
        public:
            vector<int> postorderTraversal(TreeNode* root) {
                vector<int> res;
                if(root == nullptr) return res;
                TreeNode* p = root;
                stack<TreeNode*> s;
                do{
                    while(p){
                        s.push(p);
                        res.push_back(p->val);
                        p = p->right;
                    }
                    p = s.top();
                    s.pop();
                    p = p->left;
                }while(p!=nullptr || !s.empty());
                reverse(res.begin(),res.end());
                return res;
            }
        };

Log in to reply
 

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