Leetcode 103: 二叉樹的鋸齒形層序遍歷

問題描述：
給定一個二叉樹，返回其節點值的鋸齒形層序遍歷（即第一層從左到右，第二層從右到左，第三層從左到右，依此類推）。

---

適合面試的解法：廣度優先搜索 + 雙端隊列

解法特點：

1. 廣度優先搜索（BFS）： 通過層序遍歷按層處理節點，確保節點遍歷的層次性。
2. 雙端隊列（Deque）： 通過雙端隊列控制節點值的加入順序，實現鋸齒形效果。
   • 從左到右：直接將節點值加入隊列的尾部。
   • 從右到左：將節點值插入隊列的頭部。
3. 用 BFS 控制每層的遍歷順序，用雙端隊列處理結果的鋸齒形排序。

適合面試的原因：

• 時間復雜度 (O(n))，空間復雜度 (O(n))，效率高且易于實現。
• 展現了靈活的隊列操作，是樹和 BFS 綜合應用的常見場景。

---

解法思路

核心步驟：

1. 初始化：

   • 使用隊列 Queue<TreeNode> 來管理每層的節點。
   • 定義標志變量 leftToRight 用來判斷當前層的遍歷方向。

2. 層序遍歷：

   • 遍歷每一層節點：
     • 如果 leftToRight = true，將節點值加入到當前層結果的尾部；
     • 如果 leftToRight = false，將節點值插入到當前層結果的頭部。
   • 將當前層的結果加入最終結果列表。

3. 翻轉方向：

   • 每處理完一層后，翻轉 leftToRight，切換從左到右或從右到左的方向。

---

代碼模板

方法：廣度優先搜索 + 雙端隊列

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result; // 如果樹為空，直接返回空列表Queue<TreeNode> queue = new LinkedList<>(); // BFS 隊列queue.offer(root);boolean leftToRight = true; // 初始遍歷方向是從左到右while (!queue.isEmpty()) {int levelSize = queue.size();Deque<Integer> levelList = new LinkedList<>(); // 雙端隊列存儲當前層的節點值// 遍歷當前層所有節點for (int i = 0; i < levelSize; i++) {TreeNode currentNode = queue.poll();if (leftToRight) {levelList.addLast(currentNode.val); // 從左到右：添加到尾部} else {levelList.addFirst(currentNode.val); // 從右到左：添加到頭部}// 加入下一層的節點if (currentNode.left != null) queue.offer(currentNode.left);if (currentNode.right != null) queue.offer(currentNode.right);}// 將當前層的結果加入最終結果result.add(new ArrayList<>(levelList));// 翻轉方向leftToRight = !leftToRight;}return result;}
}

---

代碼詳細注釋

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {// 定義最終結果列表List<List<Integer>> result = new ArrayList<>();// 特殊邊界條件：如果樹為空，直接返回if (root == null) return result;// 初始化 BFS 隊列和方向標記Queue<TreeNode> queue = new LinkedList<>();queue.offer(root); // 將根節點加入 BFS 隊列boolean leftToRight = true; // 起始從左到右遍歷// BFS 遍歷二叉樹的每一層while (!queue.isEmpty()) {int levelSize = queue.size(); // 當前層的節點數Deque<Integer> levelList = new LinkedList<>(); // 使用雙端隊列保存當前層結果for (int i = 0; i < levelSize; i++) {TreeNode currentNode = queue.poll(); // 從隊列中取出當前節點// 根據遍歷方向將節點值添加到雙端隊列if (leftToRight) {levelList.addLast(currentNode.val); // 從左到右時，添加到隊尾} else {levelList.addFirst(currentNode.val); // 從右到左時，添加到隊頭}// 將當前節點的左右孩子加入隊列if (currentNode.left != null) {queue.offer(currentNode.left);}if (currentNode.right != null) {queue.offer(currentNode.right);}}// 將雙端隊列的結果轉換為列表，加入最終結果result.add(new ArrayList<>(levelList));// 翻轉方向leftToRight = !leftToRight;}return result; // 返回最終結果}
}

---

復雜度分析

時間復雜度：

• 每個節點僅被訪問一次，時間復雜度為 (O(n))，其中 (n) 是樹中節點總數。

空間復雜度：

• BFS 隊列最多存儲一層的節點，最壞情況是 (O(n))。
• 使用雙端隊列臨時存儲每層結果，復雜度為 (O(w))，其中 (w) 是二叉樹的最大寬度。
  綜合空間復雜度為 (O(n))。

---

測試用例

示例 1：

輸入:3/ \9  20/  \15   7輸出:
[[3],[20,9],[15,7]
]

---

示例 2：

輸入:1/ \2   3/ \
4   5輸出:
[[1],[3,2],[4,5]
]

---

示例 3：

輸入: null
輸出: []

---

如何快速 AC（面試技巧）

1. 清晰解釋 BFS 對二叉樹的層序遍歷

• BFS 利用隊列按層層處理節點，巧妙地分離層次關系。
• 在片段中添加「左右翻轉」是實現鋸齒形遍歷的核心技巧。

2. 靈活使用雙端隊列

• 明確說明為什么使用雙端隊列：
  • 從左到右時添加到隊尾；
  • 從右到左時插入到隊頭。

3. 時間和空間復雜度分析

• 說明 BFS 遍歷節點的線性開銷 (O(n))，無多余操作，非常高效。

4. 特殊情況處理

• 空樹（根節點為 null）時，應返回空結果。

---

總結

適合面試的解法：廣度優先搜索 + 雙端隊列

• 女人拆分思路：利用 BFS 分層處理節點，用雙端隊列處理鋸齒效果。
• 時間復雜度 (O(n))、空間復雜度 (O(n))，是最優解決方案。

如何快速 AC：

1. 清晰實現 BFS，按層處理樹節點；
2. 雙端隊列解決鋸齒效果，結合方向標記靈活轉換；
3. 完整測試，涵蓋空樹和各種復雜結構樹。

這種高效解法邏輯清晰，非常適合面試場景！