My JAVA AC Solution Using Stack, simple idea


  • 1
    F

    The idea is to use two stacks, one to store nodes, another to store the status whether this node's right subtree has been visited. If yes, just pop it. If not, visit the right node and change this node's status.

     public class Solution {
            public List<Integer> postorderTraversal(TreeNode root){
                List<Integer> result = new LinkedList<Integer>();
                
                if (root == null){
                    return result;
                }
                    
                Stack<TreeNode> s1 = new Stack<TreeNode>();
                Stack<Integer> s2 = new Stack<Integer>();
                s1.push(root);
                s2.push(0);
                root = root.left;
                
                while (!s1.empty()){
                    while (root != null){
                        s1.push(root);
                        s2.push(0);
                        root = root.left;
                    }
                    
                    if (s2.peek() == 1){
                        result.add(s1.pop().val);
                        s2.pop();
                    }
                    
                    else{
                        s2.pop();
                        s2.push(1);
                        root = s1.peek().right;
                    } 
                }
                return result;
            }
        }

Log in to reply
 

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