medium
Binary Tree Level Order Traversal
Given the root of a binary tree, return its node values grouped by depth: one list per level, from the root level downward and left to right within a level.
Constraints
- 0 ≤ number of nodes ≤ 2000
- -1000 ≤ node value ≤ 1000
Examples
in: root = [3,9,20,null,null,15,7]
out: [[3],[9,20],[15,7]]
Recognition clues
- Output organised by level
- Process nodes in order of distance from the root
- Queue where each round consumes exactly one level
Pattern
Breadth-First SearchBFS explores in rings of increasing distance, so the first time it reaches a node it has found a shortest path in terms of edge count. "Minimum number of moves" on any state space where each move costs 1 is BFS, whether the states are grid cells, words, or puzzle configurations.
Solution
Put the root in a queue. While the queue is non-empty, record its current size s, pop exactly s nodes, appending their values to a new level list and pushing their children. After the round, append the level list to the result. Sizing each round by the queue length is what separates levels cleanly.
time O(n)space O(w) where w is the widest level
Alternative approaches
- DFS carrying a depth parameter and appending to
result[depth]also works and uses O(h) stack instead of O(w) queue.
Code it yourself
Solve in
Hints: