Zigzag through the rows
Read the rows of a tree left to right, then right to left, alternating, by flipping every second row after the level order walk. About 12 minutes.
Normal walk, flip some rows
A zigzag order reads the first row left to right, the second row right to left, the third left to right again, and so on.
You already know how to read the rows left to right. Keep that walk exactly as it is. Count the rows, and when a row's number is odd, reverse the finished row before adding it to the answer.
if level % 2 == 1:
row.reverse()
out.append(row)
level += 1- result
- [[1]]
Row 0 is read left to right: 1.
Do not flip the children
The reversal happens only to the list of values for the answer. The queue must still add each node's left child before the right child, so that every row is collected in its natural order first.
An empty tree returns an empty list. A tree with a single node returns one row with one value, which is the same in both directions.
row = []
for _ in range(len(q)):
node = q.popleft()
row.append(node.val)In a zigzag order, which rows are reversed after collecting them left to right?
- AThe rows numbered 1, 3, 5 and so on
- BThe rows numbered 0, 2, 4 and so on
- CAll rows
Show the answer
The rows numbered 1, 3, 5 and so on. The first row, number 0, is left to right, so the direction flips on every second row after it.
Binary tree zigzag level order traversal
Given the root of a binary tree, return its zigzag level order traversal: the values of the nodes level by level, where the first level is read from left to right, the second from right to left, the third from left to right again, and so on.
root = [3, 9, 20, null, null, 15, 7] → [[3], [20, 9], [15, 7]]
0 ≤ number of nodes ≤ 2,000 · -100 ≤ node.val ≤ 100