An easy iteration solution works if no duplicate values in the tree


  • 3
    S

    I got passed a neatly designed iteration solution that is borrowed from another post. It pushes each node two times into the stack. When we pop up a node with same value as the next node in the stack, it is going down the tree. Otherwise, it is going up. I see that this method will fail if some duplicate values exist on the tree. However, it passed around the OJ tests. I guess there is not any such special case in the tests. For example: {2, 2, #, 2, #, #, #}. Anyway, it is good to know such a solution there.

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

  • 7
    W

    very good idea, and if we change

    if (!s.empty() && cur->val == s.top()->val)

    to

    if (!s.empty() && cur == s.top())

    i think this will solve duplicate values cases


  • 0
    S

    You are awesome! I think it works since the pointers are unique to each node.


  • 0
    J

    Would it fail if the leaf node has left = NULL and right = NULL?


  • 0
    L

    The key is to trace whether a node has been expanded. I use an extra variable to do this.
    The observation is that if a node has been expanded, then the most recently popped node must be its left or right child. This voids doubling the stack.

    Here is my code.

     public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(root == null) return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        TreeNode pre = null;  // track the most recently popped node
        while(!stack.empty()){
            TreeNode n = stack.peek();
            if(n.left == null && n.right == null){
                res.add(n.val);
                pre = n;
                stack.pop();
                continue;
            }
            if(pre != null && (n.left == pre || n.right == pre)){
                res.add(n.val);
                pre = n;
                stack.pop();
            }
            else{
                if(n.right != null) stack.push(n.right);
                if(n.left != null) stack.push(n.left);
            }
        }
        return res;
    }
    

  • 0
    S

    The leaf node is supposed to have two NULL children. So I am not sure I get your point.


  • 0
    S

    You are right! Your solution minimized the stack size. I shortened it after I read your code. Thanks for your comments.

    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(root == null) return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        TreeNode pre = null;  // track the most recently popped node
        while(!stack.empty()){
            TreeNode n = stack.peek();
            
            // we print cur node when it is a leaf node, or pre is a child of cur node
            if(n.left == null && n.right == null || 
                  pre != null && 
                  (n.left == pre || n.right == pre)){ 
                res.add(n.val);
                pre = n;
                stack.pop();
            }
            else{
                if(n.right != null) stack.push(n.right);
                if(n.left != null) stack.push(n.left);
            }
        }
        return res;
    }

Log in to reply
 

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