Iterative Java Solution using 1 stack and without reversing


  • -1
    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            
            Stack<TreeNode> stack = new Stack<TreeNode>();
    
            List<Integer> result = new ArrayList<Integer>();
            
            if(root == null)
            return result;
            
            stack.push(root);
            
            TreeNode node = root,lastPopped = null;
            
            
            while (!stack.empty())
            {
                node = stack.peek();
                
                if(node.right != null)
                    stack.push(node.right);
                
                if(node.left!=null)
                    stack.push(node.left);
                
                if(node.left == null && node.right == null)
                {
                    while(!stack.empty())
                    {
                        lastPopped = stack.pop();                
    
                        result.add(lastPopped.val);
    
                        if(!stack.empty() && stack.peek().left!=lastPopped && stack.peek().right!=lastPopped)
                            break;
                    }               
                }       
            }
           
           return result;
        }
    }

Log in to reply
 

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