Space
Open
From Fieldwork
Scales
Archive
The Strategy: Standard Traversal, Alternating Storage
Imagine you are walking down the tree level by level.
The Queue: Always process nodes from Left to Right. This keeps your traversal logic simple and consistent.
The Result List: This is where you handle the zigzag.
Even Levels (L $\to$ R): Append values to the end of the level's list.
Odd Levels (R $\leftarrow$ L): Insert values at the front of the level's list (or just reverse the list at the end).
class Solution:
def zigzagLevelOrder(self, root):
if not root:
return []
results = []
queue = deque([root])
left_to_right = True # The toggle flag
while queue:
level_size = len(queue)
current_level_values = deque() # Use deque for O(1) front insertions
for _ in range(level_size):
node = queue.popleft()
# PRESENTATION LOGIC: Handle the zigzag
if left_to_right:
current_level_values.append(node.val)
else:
current_level_values.appendleft(node.val)
# TRAVERSAL LOGIC: Always standard L -> R
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Add the current level to results and toggle the flag
results.append(list(current_level_values))
left_to_right = not left_to_right
return resultsPractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode