Push to stack twice to distinguish coming back from left or right. Simple and straightforward


  • 0
    M
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode p = root;
            
            while(!stack.isEmpty() || p != null) {
                if(p != null) {
                    stack.push(p);  // will be popped when coming back from the right
                    stack.push(p);  // will be popped when coming back from the left
                    p = p.left;
                } else {
                    TreeNode node = stack.pop();
                    if (!stack.isEmpty() && node == stack.peek())
                    {
                        // coming back from the left, going right
                        p = node.right;   
                    }
                    else 
                    {
                        // coming back from the right, we are done with the node
                        result.add(node.val);
                        p = null;
                    }
                }
            }
            
            return result;
        }
    

Log in to reply
 

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