NeetCode #434LC-103MediumTrees
← Back to All Problems#434 · #103 · Binary Tree Zigzag Level Order Traversal(二叉树的锯齿形层序遍历)
📌 Problem Statement & Constraints
Given the root of a binary tree, return its zigzag level-order traversal: levels alternate between left-to-right and right-to-left, starting with left-to-right. Constraints: the number of nodes is in
[0, 2000], -100 <= Node.val <= 100.💡 Core Algorithmic Approaches
- A standard BFS collects each level's values left to right.
- Reverse the collected level on every other level (the odd-indexed ones).
- Flipping a boolean flag per level tracks the direction.
- An alternative uses a deque and appends to the front or back depending on the direction, avoiding the reversal.
💻 Benchmark Python3 Implementation
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
from collections import deque
if not root:
return []
res = []
q = deque([root])
left_to_right = True
while q:
n = len(q)
level = []
for _ in range(n):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if not left_to_right:
level.reverse() # flip the even levels
res.append(level)
left_to_right = not left_to_right
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): every node is visited once and each level is reversed at most once.
💾 Space Complexity
O(w) for the widest level.
⚠️ Interview Pitfalls & Follow-ups
- Reversing the wrong levels: the first level (index 0) is left-to-right, so odd indices are reversed.
- Reversing the children before pushing them: that changes the traversal order rather than the output order and breaks the next level.
- Using a single
level.reverse()on the queue: the queue must not be mutated. - Forgetting the empty-tree case: an empty tree has an empty result.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.