The Authentic Iterative Post Order Traversal Java Solution


  • 2
    M

    I think this is the real authentic Post Order Traversal solution, because it DID traverse in a post order manner.

    Besides current, this solution use two extra node: prev and peek.

    • prev help make sure current node is stored once its right branch is explored.
    • peek help make sure current node do not re-visit its left branch once its left branch is explored.
    public List<Integer> postOrder(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode current = root;
            TreeNode prev = null;
            TreeNode peek = null;
            while (current != null || !stack.isEmpty()) {
                if (current != null) {
                    stack.push(current);
                    current = current.left;
                }
                else {
                    peek = stack.peek();
                    if (peek.right == null || peek.right == prev) {    // Did not update current 
                        result.add(peek.val);
                        prev = stack.pop();
                    }
                    else current = peek.right;    // Update current so that current will then move leftward.
                }
            }
            return result;    
    }
    

Log in to reply
 

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