LeetCode算法题(Go语言实现)_37

题目

给你一棵以 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. 工程优化

• 迭代实现：用栈模拟递归，减少函数调用开销。
• 并行处理：对子树进行并行计算，提升大规模数据处理效率。