Iterative Java 2ms clean solution using stack


  • 0
    M
    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            List<Integer> result = new ArrayList<>();
            if( root == null )
                return result;
            TreeNode prev = null, curNode = root;
            stack.push(curNode);
            while( !stack.isEmpty() )
            {
                curNode = stack.peek();
                // Traversing from top to bottom??
                if( prev == null || prev.left == curNode || prev.right == curNode )
                {
                    if( curNode.left != null )
                    {
                        stack.push(curNode.left);
                    }
                    else if( curNode.right != null )
                    {
                        stack.push(curNode.right);
                    }
                    else
                    {
                        //Push it to result if it is a leaf node. Pop it from stack only when it is pushed to the result.
                        stack.pop();
                        result.add(curNode.val);
                    }
                }
                // Traversing from bottom to top. If prev is left or right child of curNode.
                // If it is a right child, print the curNode or else process the right node.
                else 
                {
                    if( curNode.left == prev )
                    {
                        if(curNode.right != null )
                            stack.push( curNode.right);
                    }
                    else
                    {
                        stack.pop();
                        result.add(curNode.val);
                    }
                }
                 prev = curNode;
            }
            return result;
            
        }
    }
    

Log in to reply
 

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