305. Find Leaves of Binary Tree
You receive root, the root of a binary tree (each TreeNode has val, left, right). Imagine peeling the tree like an onion: collect every current leaf, remove those leaves, and repeat on what remains until the tree is empty. The root is always collected in the final round.
Return the rounds as a list of lists: the first inner list holds the values removed in round 1 (the original leaves), the second holds round 2, and so on.
Canonical order: within a round, list values in the order the nodes appear from left to right in the original tree — a node in a left subtree comes before any node in the subtree to its right.
Example 1:
Input: root = [1, 2, 3, 4, 5]
Output: [[4, 5, 3], [2], [1]]
Explanation: Round 1 removes the leaves 4, 5, and 3. That turns 2 into a leaf, so round 2 removes it. Round 3 removes the now-bare root 1.
Example 2:
Input: root = [1]
Output: [[1]]
Explanation: The root is itself a leaf, so the single round removes it.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -100 ≤ Node.val ≤ 100
Hints:
Simulating the peeling works: walk the tree, collect leaves, physically detach them, repeat until nothing is left. What is the worst-case cost of re-walking a chain-shaped tree every round?
Ask a different question per node: in which round is *this* node removed? A leaf goes in round 1, and any other node goes exactly one round after the later-removed of its children — that number is the node's height.
Compute height in one postorder pass (height = 1 + max(height(left), height(right)), with null = -1) and drop each node into the bucket at index height. Postorder naturally appends left-subtree nodes first, matching the required left-to-right order.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, 4, 5]
Expected output: [[4, 5, 3], [2], [1]]