Easy C++ Iterative Solution by Pushing Twice


  • 0
    L

    This is a classical problem, recursive version is trivial, but iterative solution may need some thinking. Typical ways of solving this problem iteratively has been discussed a lot, the following solution may be a less common one:

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> res;
            stack<TreeNode*> s;
            if(!root) 
                return res;
            s.push(root),s.push(root);//push twice
            while(!s.empty()){
                root=s.top();
                s.pop();
                if(!s.empty()&&root==s.top()){
                    if(root->right) s.push(root->right),s.push(root->right);//push twice
                    if(root->left) s.push(root->left),s.push(root->left);//push twice
                }
                else
                    res.push_back(root->val);//visit the node
            }
            return res;
        }
    };
    

    Each time we push twice, then we do pop and check whether the element matches the top element in stack. If they're equal, it means the elements's children haven't been visited yet and we need to do push again. The order of push should be root -> right -> left because we need a sequence of left -> right -> root after pop.


Log in to reply
 

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