MediumRating 1576

103. Binary Tree Zigzag Level Order Traversal

treebreadth-first-searchbinary-tree

在 LeetCode 上作答 ↗

解題說明

Binary Tree Zigzag Level Order Traversal

題目描述：給定一棵二元樹的根節點，返回其節點值的「鋸齒形」層序遍歷結果。具體而言，第 0 層從左到右，第 1 層從右到左，第 2 層從左到右，以此交替。

解題思路：以標準 BFS 為基礎，使用一個布林旗標 left_to_right 追蹤當前層的遍歷方向（初始為 true）。每層處理流程如下：

記錄當前層的節點數 sz，依序彈出 sz 個節點並收集節點值到 level 陣列。
若當前層應「從右到左」（left_to_right == false），則將 level 陣列反轉（reverse）。
將 level 加入結果，並切換 left_to_right 的值。

另一個等效做法是用 deque：從左到右的層直接 push_back，從右到左的層則 push_front，避免反轉操作，但兩者時間複雜度相同。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個節點恰好入 queue 和出 queue 各一次；每層的反轉操作耗時 O(w)（w 為當前層寬度），所有層的反轉總和仍為 O(n)。

空間複雜度：O(w) — queue 同時最多存放一層的節點，w 為樹的最大寬度；輸出陣列不計入額外空間，若計入則為 O(n)。

虛擬碼

1. If root is null: return empty result
2. Initialize queue q with root; left_to_right = true
3. While q is not empty:
   a. sz = q.size()
   b. Initialize empty vector level
   c. For i from 0 to sz-1:
      i.  node = q.front(); q.pop()
      ii. Append node.val to level
      iii. If node.left: push to q
      iv.  If node.right: push to q
   d. If not left_to_right: reverse(level)
   e. Append level to result
   f. left_to_right = !left_to_right
4. Return result

其他解法

方法一：BFS + deque 插入方向控制 每層使用 deque<int> 收集節點值。若當前層從左到右，使用 push_back；若從右到左，使用 push_front。不需要反轉操作，邏輯上更直觀，但 deque 的常數開銷略大。時間複雜度 O(n)，空間複雜度 O(w)。

方法二：雙端 Queue（deque）BFS 控制入隊方向 改變節點本身的入隊方向：從右到左的層，將子節點以「右先左後」的順序推入 queue，讓下一層自然以正確順序排列。但這需要對「下一層的下一層」再次調整，追蹤較複雜，不如直接在收集後反轉清晰。

方法三：DFS 搭配層級索引 用 DFS 遍歷樹，傳遞 level 參數，依層奇偶決定是否將節點值插入到對應 result[level] 的頭部或尾部。時間複雜度 O(n)，空間複雜度 O(h)（遞迴堆疊），但在寬樹情況下比 BFS 省記憶體。

延伸思考

若要求輸出「螺旋形」（spiral）而非鋸齒形——即從外圈到內圈依序讀取所有節點值，這個問題要如何轉換和解決？
在 deque 插入方向方法（方法一）中，push_front 的時間複雜度是 O(1)，而 vector 的 reverse 是 O(w)。在哪些情況下 deque 方法具有實際優勢？
若樹可以非常寬（例如最後一層有 10^6 個節點），而每層收集後都要反轉，反轉操作的總成本是多少？請用求和公式分析是否仍為 O(n)。