---
title: "103. Binary Tree Zigzag Level Order Traversal"
url: "https://laigary.com/interview/coding/103-binary-tree-zigzag-level-order-traversal"
type: "note"
section: "coding"
date: "2025-03-25"
updated: "2026-07-26"
tags: ["Tree", "Breadth-First Search"]
---

# 103. Binary Tree Zigzag Level Order Traversal

[103\. Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/)

層序遍歷，但方向要交替：第 0 層由左到右、第 1 層由右到左、第 2 層又由左到右⋯⋯

## 思路

看到「zigzag」很容易第一個反應是「那我的佇列要不要反著走？」—— **不要**。

正確的想法是：**遍歷方式完全不變，只是輸出前把奇數層的陣列翻過來。**

BFS 本身照常一層一層走（見 [102. Binary Tree Level Order Traversal](/interview/coding/102-binary-tree-level-order-traversal)），拿到那一層的陣列之後再決定要不要 `[::-1]`。把「怎麼走」和「怎麼輸出」分開，題目就從「特殊的遍歷」變成「普通的遍歷 + 一行後處理」。

如果真的去動佇列的方向，會發現子節點的入列順序也要跟著反轉，兩個方向互相糾纏，非常容易寫錯 —— 這是這題最主要的陷阱。

剩下就是分層的老問題：**進迴圈前先把 `len(q)` 固定下來**，那個數字就是這一層的節點數，迴圈裡新加入的下一層不會被算進去。

## 解題方向

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        if not root:
            return []
        
        q = deque([root])
        ans = []
        count = 0
        
        
        while q:
            size = len(q)
            curr = []
            for _ in range(size):
                node = q.popleft()
                curr.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if count%2 == 1:
                curr = curr[::-1]
            
            count += 1
            ans.append(curr)
        
        return ans
```

`count` 就是層數，用 `count % 2 == 1` 判斷奇數層。其實不需要額外的變數 —— **`len(ans)` 就是目前已經完成的層數**，所以 `if len(ans) % 2 == 1` 效果一樣，少一個要維護的狀態。兩種都好，看你喜歡哪種。

**另一種寫法是用 `deque` 直接往前塞**，省掉最後的反轉：

```python
            curr = deque()
            for _ in range(size):
                node = q.popleft()
                if count % 2 == 0:
                    curr.append(node.val)        # 由左到右
                else:
                    curr.appendleft(node.val)    # 由右到左
```

複雜度一樣（`[::-1]` 和 `appendleft` 都是每個元素一次操作），差別只在風格。`[::-1]` 比較好讀，`appendleft` 少建一個暫時的 list。

## 補充

**同一個 BFS 骨架的變形**，差別只在「每一層拿到之後做什麼」：

| 題目 | 每層做什麼 |
|---|---|
| [102. Level Order](/interview/coding/102-binary-tree-level-order-traversal) | 直接收整層 |
| **103 這題** | 奇數層反轉 |
| [199. Right Side View](/interview/coding/199-binary-tree-right-side-view) | 只取每層最後一個 |
| [515. Find Largest Value in Each Tree Row](/interview/coding/515-find-largest-value-in-each-tree-row) | 每層取最大值 |
| [1302. Deepest Leaves Sum](/interview/coding/1302-deepest-leaves-sum) | 只留最後一層求和 |

骨架整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

- 時間 $O(n)$ — 每個節點進出佇列各一次；所有層的反轉加起來也只是把每個節點各碰一次，仍然是 $O(n)$
- 空間 $O(w)$ — 佇列裡最多裝下最寬的一層，`w` 是最大寬度；完全二元樹的最後一層約 $n/2$，所以最壞是 $O(n)$

其中 `n` 是節點數、`w` 是樹的最大寬度（不含輸出的 `ans`）。

反轉那一步值得主動說明：**它不會讓複雜度變成 $O(n \log n)$**，因為每一層只反轉一次，所有層的長度加起來就是 `n`。