The problem
Given the root of a binary tree, return its values level by level: a list per level, from the top down, each read left to right.
Examples
01
- Input
root = [3, 9, 20, null, null, 15, 7]
- Output
[[3], [9, 20], [15, 7]]
02
- Input
root = [1]
- Output
[[1]]
03
- Input
root = []
- Output
[]
Constraints
- 0 ≤ number of nodes ≤ 2000
- −1000 ≤ Node.val ≤ 1000
The idea
Breadth-first search visits a tree level by level. It keeps a queue — a line where the first in is the first out — of nodes waiting to be visited: take one from the front, add its children at the back.
To keep levels apart, note how many nodes are in the queue at the start of a level: exactly that many belong to it. Take that many, collect their values, and their children form the next level behind them.
- Time
- O(n)
- Space
- O(w) — the widest level, up to about n ÷ 2
Solution · every language run against every case
class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: out = [] queue = deque([root] if root else []) while queue: level = [] for _ in range(len(queue)): # exactly the nodes of this level node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) out.append(level) return out