⚡Flashcard Drill➔
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

  1. A standard BFS collects each level's values left to right.
  2. Reverse the collected level on every other level (the odd-indexed ones).
  3. Flipping a boolean flag per level tracks the direction.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems