Given the root of a binary tree, return the level order traversal of its
node values (i.e., from left to right, level by level).
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Input: root = [1]
Output: [[1]]
Input: root = []
Output: []
Constraints:
- 0 <= Number of nodes <= 2000
- -1000 <= Node.val <= 1000
Contents
- Solution — BFS with Queue
- Complexity Analysis
BFS with Queue
The key insight: at the start of each outer loop, queue.size() equals the number of nodes
at the current level. Process exactly that many nodes, then move to the next level.
Implementation steps:
- Enqueue the root.
- While the queue is non-empty, snapshot levelSize = queue.size().
- Dequeue levelSize nodes, collect their values, enqueue their children.
- Add the level's values to the result list.
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size(); // nodes at this level
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
Trace through Example 1: root = [3,9,20,null,null,15,7]
| Outer iteration | Level size | Nodes dequeued | Level values |
|---|
| 1 | 1 | 3 | [3] |
| 2 | 2 | 9, 20 | [9, 20] |
| 3 | 2 | 15, 7 | [15, 7] |
- Time: O(n) — each node is enqueued and dequeued exactly once.
- Space: O(n) — the queue holds at most n/2 nodes (widest level of a complete binary tree).