0145.md

145. Binary Tree Postorder Traversal

Level:

Topic:

Similar Problem:

• 94. Binary Tree Inorder Traversal
• 144. Binary Tree Preorder Traversal

Question

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Input: root = [1,null,2,3]
Output: [3,2,1]

Intuition

Recursive:

• Node -> Right -> Left

Iterative:

DFS postorder

Stack

1. push node into stack and traverse to the very left
2. check the topmost's right child
   • if it's just been visited or null
     • pop it and mark it as just been visited
     • it's time to add the node val
   • else
     • traverse that node (loop to step 1)
     • (it will be addd when checking its left childs)

Code

Time: O(n)
Space: O(n)

Iterative

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<Integer>();

    if(root == null) {
        return ans;
    }

    Stack<TreeNode> stack = new Stack<TreeNode>();
    // We will have a pointer to the recently popped node
    TreeNode curr = root, prev = null;

    while(curr != null || !stack.isEmpty()) {
        // Keep on iterating towards the leftmost node
        while(curr != null) {
            stack.push(curr);
            curr = curr.left;
        }

        // If there is no right child
        // or right child is the one that we recently visited
        // it means we have traversed all the nodes of stack.peek()
        TreeNode right = stack.peek().right;
        if(right == null || right == prev) {
            // we will update the prev node
            prev = stack.pop();
            ans.add(prev.val);
        } else {
            // Otherwise we will visit the right child.
            curr = right;
        }
    }

    return ans;
}

Recursive

List<Integer> ans = new ArrayList<>();

public List<Integer> postorderTraversal(TreeNode root) {
    postorder(root);
    return ans;
}

private void postorder(TreeNode root) {
    if (root == null)
        return ;
    postorder(root.left);
    postorder(root.right);
    ans.add(root.val);
}