share my real iterative solution


  • 1
    J
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> ret;
            stack<TreeNode*> s;
            while (root){
                s.push(root);
                if (root->left) root = root->left;
                else root = root->right;
            }
            
            while (s.size()){
                // Top of stack s is the next one to iterate.
                TreeNode* p = s.top(); s.pop();
                ret.push_back(p->val);
                // If p is the root of the input tree, it would be empty.
                if (s.empty()){
                    break;
                }
                
                TreeNode* rt = s.top(); s.pop();
                // p is the right child, or there is no right child for p's father.
                if (!rt->right || p==rt->right) { s.push(rt); continue;}
                // p is the left child
                else{
                    while (rt){
                        s.push(rt);
                        // Avoid of adding p itself back into stack s
                        if (p!=rt->left && rt->left) rt = rt->left;
                        else if(p!=rt->right && rt->right) rt = rt->right;
                        else {rt=NULL;}
                    }
                }
                
            }
            
            return ret;
        }
    };
    

Log in to reply
 

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