Read the tree row by row
List the nodes of a binary tree one level at a time, using a queue and counting how many nodes are in the current row. About 14 minutes.
A queue serves the oldest first
Depth-first walks go deep before they go wide. To read a tree row by row, you want the opposite: finish a whole level before the next one. A queue does that, because the oldest waiting node is served first.
Start with the root in the queue. Take a node from the front, record it, and add its left and right children to the back. Children always queue up behind their parents' whole row.
node = q.popleft()
row.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)- queue
- [9, 20]
- result
- [[3]]
Row 1: the queue holds only 3. Take it and queue its children 9 and 20.
Where does a row end
The queue holds a mix: the rest of this row and the start of the next. To split the rows, note the queue's size when a row begins. That is exactly the number of nodes in the row.
Process that many nodes, collecting a row. The children they add land behind, and become the next row. Repeat until the queue is empty. An empty tree has no rows at all.
while q:
row = []
for _ in range(len(q)):
...
out.append(row)Why take the queue's size at the start of each row?
- AIt says how many nodes belong to this row, since children added later belong to the next one
- BIt makes the loop faster
- CIt tells you whether the tree is empty
Show the answer
It says how many nodes belong to this row, since children added later belong to the next one. Children join the back of the queue while the row is being processed.
Binary tree level order traversal
Given the root of a binary tree, return its level order traversal: the values of the nodes level by level, from left to right within each level, as a list of lists. An empty tree gives an empty list.
root = [3, 9, 20, null, null, 15, 7] → [[3], [9, 20], [15, 7]]
0 ≤ number of nodes ≤ 2,000 · -1,000 ≤ node.val ≤ 1,000