題目

給你一棵以 root 為根的二叉樹，二叉樹中的交錯路徑定義如下：
選擇二叉樹中 任意 節點和一個方向（左或者右）。
如果前進方向為右，那么移動到當前節點的的右子節點，否則移動到它的左子節點。
改變前進方向：左變右或者右變左。
重復第二步和第三步，直到你在樹中無法繼續移動。
交錯路徑的長度定義為：訪問過的節點數目 - 1（單個節點的路徑長度為 0 ）。
請你返回給定樹中最長 交錯路徑 的長度。

一、代碼實現

func longestZigZag(root *TreeNode) int {maxLen := 0var dfs func(*TreeNode) (int, int)dfs = func(node *TreeNode) (int, int) {if node == nil {return 0, 0}_, leftRight := dfs(node.Left)rightLeft, _ := dfs(node.Right)currentLeft, currentRight := 0, 0if node.Left != nil {currentLeft = leftRight + 1}if node.Right != nil {currentRight = rightLeft + 1}if currentLeft > maxLen {maxLen = currentLeft}if currentRight > maxLen {maxLen = currentRight}return currentLeft, currentRight}dfs(root)return maxLen
}

二、算法分析

1. 核心思路

• 動態規劃（后序遍歷）：每個節點維護兩個狀態，表示從該節點出發下一步向左或向右的最長交錯路徑長度。
• 狀態轉移：當前節點的左方向長度由左子節點的右方向長度加1，右方向長度由右子節點的左方向長度加1。
• 全局最大值：在遍歷過程中不斷更新最長路徑長度。

2. 關鍵步驟

1. 遞歸終止：空節點返回 (0, 0)。
2. 狀態計算：根據左右子節點返回的狀態計算當前節點的左右方向長度。
3. 更新最大值：比較并更新全局最長路徑長度。
4. 返回狀態：返回當前節點的左右方向長度供父節點使用。

3. 復雜度

指標	值	說明
時間復雜度	O(n)	每個節點遍歷一次
空間復雜度	O(h)	遞歸棧空間，h為樹的高度

三、圖解示例

四、邊界條件與擴展

1. 特殊場景驗證

• 單節點樹：直接返回0。
• 完全左斜樹：所有節點只有左子節點，最長路徑為1。
• 交替路徑：如 1→2→3→4→5，路徑長度為4。

2. 多語言實現

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def longestZigZag(self, root: TreeNode) -> int:self.max_len = 0def dfs(node):if not node:return (0, 0)left_left, left_right = dfs(node.left)right_left, right_right = dfs(node.right)current_left = left_right + 1 if node.left else 0current_right = right_left + 1 if node.right else 0self.max_len = max(self.max_len, current_left, current_right)return (current_left, current_right)dfs(root)return self.max_len

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}class Solution {private int maxLen = 0;public int longestZigZag(TreeNode root) {dfs(root);return maxLen;}private int[] dfs(TreeNode node) {if (node == null) return new int[]{0, 0};int[] left = dfs(node.left);int[] right = dfs(node.right);int currentLeft = node.left != null ? left[1] + 1 : 0;int currentRight = node.right != null ? right[0] + 1 : 0;maxLen = Math.max(maxLen, Math.max(currentLeft, currentRight));return new int[]{currentLeft, currentRight};}
}

五、總結與擴展

1. 核心創新點

• 狀態定義：通過左右方向狀態分離，避免路徑方向沖突。
• 后序遍歷：自底向上遞推，確保子問題先解。

2. 擴展應用

• 多方向路徑：擴展到多叉樹，增加狀態維度。
• 加權路徑：節點帶權重，求最大權重路徑。
• 實時更新：處理動態樹結構，增量維護狀態。

3. 工程優化

• 迭代實現：用棧模擬遞歸，減少函數調用開銷。
• 并行處理：對子樹進行并行計算，提升大規模數據處理效率。