103. Binary Tree Zigzag Level Order Traversal

──────────────────────────────────────────────────────────────────────

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

思路

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

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

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

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

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

解題方向

# 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 直接往前塞，省掉最後的反轉：

            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	直接收整層
103 這題	奇數層反轉
199. Right Side View	只取每層最後一個
515. Find Largest Value in Each Tree Row	每層取最大值
1302. Deepest Leaves Sum	只留最後一層求和

骨架整理見 Tree 遍歷模板。

複雜度

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

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

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