题目
给你一棵以 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. 关键步骤
- 递归终止：空节点返回
(0, 0)。 - 状态计算：根据左右子节点返回的状态计算当前节点的左右方向长度。
- 更新最大值：比较并更新全局最长路径长度。
- 返回状态：返回当前节点的左右方向长度供父节点使用。
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. 工程优化
- 迭代实现：用栈模拟递归，减少函数调用开销。
- 并行处理：对子树进行并行计算，提升大规模数据处理效率。
