Longest ZigZag Path in a Binary Tree
題目描述
給定一棵二元樹的根節點 root，回傳最長 ZigZag 路徑的長度。ZigZag 路徑定義為：從任意節點開始，交替走左右方向。路徑長度等於邊數。
輸入: 1
/ \
1 1
\ \
1 1
/ \
1 1
\
1
輸出: 3
解釋: 右→左→右（3 條邊）
解題思路
DFS 帶方向資訊
dfs(node, left, right) 中 left 代表最後一步走左到此的 ZigZag 長度，right 同理
走左子樹
呼叫 dfs(node.left, right+1, 0)：延續上步走右的長度加 1（交替），同時重置 right 為 0
走右子樹
呼叫 dfs(node.right, 0, left+1)：延續上步走左的長度加 1（交替），同時重置 left 為 0
方向不對則重置
傳入 0 代表該方向的 ZigZag 從頭開始 — 例如連續走兩次左就不是 ZigZag
更新全域最大值
每個節點執行 maxLen = max(maxLen, left, right) 追蹤全域最優解
程式碼
C#
public class Solution {
private int maxLen = 0;
public int LongestZigZag(TreeNode root) {
Dfs(root, 0, 0);
return maxLen;
}
// left: 以此節點為終點、最後一步走左的 ZigZag 長度
// right: 以此節點為終點、最後一步走右的 ZigZag 長度
private void Dfs(TreeNode node, int left, int right) {
if (node == null) return;
maxLen = Math.Max(maxLen, Math.Max(left, right));
// 往左走：延續 right+1（上步走右，這步走左 = zigzag）
// 重置 left 為 0（因為往左走時，若下一步再走左就斷了）
Dfs(node.left, right + 1, 0);
// 往右走：延續 left+1，重置 right
Dfs(node.right, 0, left + 1);
}
}TypeScript
function longestZigZag(root: TreeNode | null): number {
let maxLen = 0;
function dfs(node: TreeNode | null, left: number, right: number): void {
if (!node) return;
maxLen = Math.max(maxLen, left, right);
dfs(node.left, right + 1, 0); // 走左：延續上步走右的長度
dfs(node.right, 0, left + 1); // 走右：延續上步走左的長度
}
dfs(root, 0, 0);
return maxLen;
}Python
def longestZigZag(root: Optional[TreeNode]) -> int:
max_len = 0
def dfs(node, left, right):
nonlocal max_len
if not node:
return
max_len = max(max_len, left, right)
dfs(node.left, right + 1, 0) # 走左：延續上步走右的長度
dfs(node.right, 0, left + 1) # 走右：延續上步走左的長度
dfs(root, 0, 0)
return max_len複雜度分析
| Time | Space | |
|---|---|---|
| 本解法 | O(n) | O(h) |
Time O(n) 是因為每個節點恰好被 DFS 訪問一次，每次做常數操作（比較和更新 maxLen）。Space O(h) 是遞迴 call stack 深度，h 為樹高。
邊界情況
- 只有根節點：沒有任何邊，ZigZag 長度為 0
- 全部偏向同一方向：如只有右子鏈
1→2→3→4，沒有方向交替，最長 ZigZag 為 0 - 完全二元樹：每個節點都有左右子，最長 ZigZag 路徑等於樹高 h（從根開始交替走）
圖解
圖表展示了 ZigZag 長度的傳遞方式：每次交替方向時長度加 1，方向不交替時重置為 0。走左時繼承 right+1（因為是上一步走右的延續），走右時繼承 left+1。
進階觀點
💡面試追問
Q: 為什麼用兩個參數 left/right 而不是一個方向標記？ A: 每個節點可能同時是兩條 ZigZag 路徑的終點 — 一條最後一步走左到此、一條最後一步走右到此。用兩個參數分別追蹤，才能在往子樹走時正確選擇延續哪條路徑。只用一個方向標記會丟失另一條路徑的資訊。
Q: 為什麼每個節點都要更新 maxLen 而不只在葉子更新？ A: ZigZag 路徑不一定終止在葉子。例如某個節點只有左子樹，從右邊來的 ZigZag 無法繼續走右延續，但這條 ZigZag 的長度可能已是全域最大。
變體題：LC 543 Diameter of Binary Tree（最長路徑，不限方向交替）。
理解測驗
🤔 走到左子節點時，為什麼 right 參數傳 0？
🤔 一棵只有右子鏈的樹（1→2→3→4），最長 ZigZag 長度是多少？