#145
Binary Tree Postorder Traversal
Easy Reverse of modified preorder
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the values of a binary tree in postorder (left subtree, right subtree, node).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: left, right, then node.
Why this works: node-right-left reversed equals left-right-node. Do a preorder with the children swapped and add to the front.
Example: tree 1 (left 2, right 3)
node-right-left: 1, 3, 2reversed: [2, 3, 1]
✦Hints open one at a time
Postorder reversed is node-right-left.
Node-right-left is preorder with the children pushed the other way round.
↗Approach
Run the stack preorder but push left before right, adding each value to the front of a LinkedList. The result is left-right-node.
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> res = new LinkedList<>();
if (root == null) return res;
Deque<TreeNode> st = new ArrayDeque<>();
st.push(root);
while (!st.isEmpty()) {
TreeNode n = st.pop();
res.addFirst(n.val); // build the answer backwards
if (n.left != null) st.push(n.left);
if (n.right != null) st.push(n.right);
}
return res;
}
}!Common mistake
Trying the one-stack "true" postorder without tracking the last visited node — easy to loop forever.
Complexity
- Time: O(n).
- Space: O(h) for the stack plus the output.
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon