simple and straightforward iterative Java solution with stack


  • 3
    H
    public class Solution {
        public List<Integer> postorderTraversal(TreeNode root) {
            Deque<TreeNode> stack = new LinkedList<>();
            List<Integer> res = new LinkedList<>();
            
            while(root != null || !stack.isEmpty()){
                if(root != null){
                    stack.push(root);
                    root = root.left;
                }
                else{
                    while(!stack.isEmpty() && stack.peek() == null){
                        stack.pop();
                        res.add(stack.pop().val);
                    }
                    if(stack.isEmpty()) break;
                    
                    root = stack.peek().right;
                    stack.push(null);
                }
            }
            
            return res;
        }
    }
    

    just push null to mark the left branch is finished.


Log in to reply
 

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