Children Before Parent
EasyTrees
Problem
A build system compiles a module only after both of its dependencies are built: first everything in the left branch, then everything in the right branch, and only then the module itself.
Given the root of a binary tree, return the values in that order (a postorder traversal), without recursion.
Example 1
- Input:
- root = [1, null, 2, 3]
- Output:
- [3, 2, 1]
3 has no dependencies, then 2 (which needs 3), then 1 (which needs 2).
Example 2
- Input:
- root = [4, 2, 6, 1, 3, 5, 7]
- Output:
- [1, 3, 2, 5, 7, 6, 4]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -1000 ≤ node.val ≤ 1000
Hint
Show the first hint
Compare postorder (left, right, root) with a modified preorder that visits root, right, left. What is the relationship?
Walkthrough
How to approach it
01Clarify before coding
- Empty tree? Return [].
- Is extra O(n) memory for the output acceptable? Yes, the output is O(n) anyway.
- Must it be a single pass? No; a reversal at the end is fine.
02Brute force
Recursive postorder: recurse left, recurse right, then record the node.
Cost: O(n) time, O(h) call stack; deep chains break Python's recursion limit.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.