MediumRating 1713

1372. Longest ZigZag Path in a Binary Tree

dynamic-programmingtreedepth-first-searchbinary-tree

在 LeetCode 上作答 ↗

解題說明

Longest ZigZag Path in a Binary Tree

題目描述：給定一棵二元樹的根節點，找出其中最長的 ZigZag 路徑長度。ZigZag 路徑是指從某個節點出發，每一步交替向左子節點或右子節點移動的路徑。路徑長度定義為路徑中的邊數（經過的節點數減一）。

解題思路：使用 DFS（深度優先搜尋）並在每個節點追蹤兩個方向的 ZigZag 長度：

定義遞迴函式 dfs(node, leftLen, rightLen)，其中 leftLen 表示從父節點往左走到此節點時，目前累積的 ZigZag 長度；rightLen 則是往右走到此節點時的累積長度。
在每個節點，更新全域最大值為 max(leftLen, rightLen)。
向左子節點遞迴時：若上一步是從父節點向右走來（rightLen + 1 代表延伸 ZigZag），則左方向帶入 rightLen + 1；右方向重置為 1（因為此時若再往右走就是連續同向，ZigZag 長度只有 1）。
向右子節點遞迴時：方向對稱處理，左方向重置為 1，右方向帶入 leftLen + 1。
整棵樹搜尋完畢後回傳全域最大值。

此做法每個節點只拜訪一次，且不需額外的資料結構，是最簡潔高效的解法。

C++ 解法

複雜度分析

時間複雜度：O(N) — 每個節點恰好被 DFS 拜訪一次，其中 N 為樹中節點總數。

空間複雜度：O(H) — 遞迴呼叫的堆疊深度等於樹的高度 H。最壞情況（退化為鏈狀樹）為 O(N)，平衡二元樹則為 O(log N)。

虛擬碼

1. Initialize global variable `ans = 0`
2. Define `dfs(node, leftLen, rightLen)`:
   a. If `node` is null, return
   b. Update `ans = max(ans, leftLen, rightLen)`
   c. Recurse left: `dfs(node.left, rightLen + 1, 1)`
      - rightLen + 1: extend zigzag (came from right, now going left)
      - 1: reset right counter (starting a new path going right from here)
   d. Recurse right: `dfs(node.right, 1, leftLen + 1)`
      - 1: reset left counter (starting a new path going left from here)
      - leftLen + 1: extend zigzag (came from left, now going right)
3. Call `dfs(root, 0, 0)`
4. Return `ans`

其他解法

方法一：回傳值 DFS O(N)：另一種設計是讓 dfs 函式回傳一個 pair {leftMax, rightMax}，表示以當前節點為起點分別往左或往右出發可達的最長 ZigZag 長度，然後在父節點合併結果。此法不需全域變數，較適合函數式風格，但每個節點需要額外建立 pair，常數倍略高。

方法二：DP on Tree O(N)：將問題轉化為樹上動態規劃，定義 dp[node][0] 為以 node 為端點、最後一步向左的最長 ZigZag，dp[node][1] 為最後一步向右的最長 ZigZag。狀態轉移為 dp[node][0] = dp[node->left][1] + 1，dp[node][1] = dp[node->right][0] + 1。此法概念直觀，與傳入參數的 DFS 本質相同，但需要額外的 hash map 或陣列儲存 DP 值，空間使用較多。

延伸思考

若路徑不必從樹的節點出發，而是可以從任意邊的中點開始，ZigZag 的定義會如何改變？解法需要做哪些調整？
如果將「ZigZag」定義推廣到 N 元樹（每個節點最多有 N 個子節點），且每次只要選擇與上一步不同的子節點方向即可，應如何修改演算法？
在本題的基礎上，若需同時回傳所有達到最長長度的 ZigZag 路徑（而非只回傳長度），應如何追蹤並輸出完整路徑？時間與空間複雜度會如何變化？

解題說明

Longest ZigZag Path in a Binary Tree

解題思路：使用 DFS（深度優先搜尋）並在每個節點追蹤兩個方向的 ZigZag 長度：

定義遞迴函式 dfs(node, leftLen, rightLen)，其中 leftLen 表示從父節點往左走到此節點時，目前累積的 ZigZag 長度；rightLen 則是往右走到此節點時的累積長度。
在每個節點，更新全域最大值為 max(leftLen, rightLen)。
向左子節點遞迴時：若上一步是從父節點向右走來（rightLen + 1 代表延伸 ZigZag），則左方向帶入 rightLen + 1；右方向重置為 1（因為此時若再往右走就是連續同向，ZigZag 長度只有 1）。
向右子節點遞迴時：方向對稱處理，左方向重置為 1，右方向帶入 leftLen + 1。
整棵樹搜尋完畢後回傳全域最大值。

此做法每個節點只拜訪一次，且不需額外的資料結構，是最簡潔高效的解法。

虛擬碼

1. Initialize global variable `ans = 0` 2. Define `dfs(node, leftLen, rightLen)`: a. If `node` is null, return b. Update `ans = max(ans, leftLen, rightLen)` c. Recurse left: `dfs(node.left, rightLen + 1, 1)` - rightLen + 1: extend zigzag (came from right, now going left) - 1: reset right counter (starting a new path going right from here) d. Recurse right: `dfs(node.right, 1, leftLen + 1)` - 1: reset left counter (starting a new path going left from here) - leftLen + 1: extend zigzag (came from left, now going right) 3. Call `dfs(root, 0, 0)` 4. Return `ans`

其他解法

延伸思考

若路徑不必從樹的節點出發，而是可以從任意邊的中點開始，ZigZag 的定義會如何改變？解法需要做哪些調整？
如果將「ZigZag」定義推廣到 N 元樹（每個節點最多有 N 個子節點），且每次只要選擇與上一步不同的子節點方向即可，應如何修改演算法？
在本題的基礎上，若需同時回傳所有達到最長長度的 ZigZag 路徑（而非只回傳長度），應如何追蹤並輸出完整路徑？時間與空間複雜度會如何變化？