You are given root, the root of a binary tree (or nothing, for an empty tree).
Return its values level by level: a list with one inner list per level, from the root's level
downwards, each holding that level's values from left to right. An empty tree gives [].
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.
Example 1
- Input
- root = [6, 2, 8, 1, 4, null, 9]
- Output
- [[6], [2, 8], [1, 4, 9]]
Example 2
- Input
- root = [1, null, 2, 3]
- Output
- [[1], [2], [3]]
Constraints
- The tree holds 0 to 2000 nodes.
- Every value is between −1000 and 1000.
Show the pattern
Trees
"Row by row from the top" is breadth-first order. Going a level at a time, the children of one level's nodes, left to right, make up the next level.
See trees in a visualiserShow the approach
Go breadth-first, one level at a time. Keep the list of nodes on the current level, starting with just the root (or nothing, for an empty tree). Each round, record that level's values, then build the next level from their children, left child before right child, node by node. Stop when a level is empty.
This is a breadth-first search in which the current level plays the part of the queue. With a real queue, the queue's length at the start of each round tells you how many nodes the level has.
Time: O(n) · Space: O(w), w the widest level