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

题目

给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
选择二叉树中 任意 节点和一个方向（左或者右）。
如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
改变前进方向：左变右或者右变左。
重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
请你返回给定树中最长 交错路径 的长度。

一、代码实现

func longestZigZag(root *TreeNode) int {
    maxLen := 0
    var 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, 0
        if 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. 复杂度

三、图解示例

四、边界条件与扩展

1. 特殊场景验证

• 单节点树：直接返回0。
• 完全左斜树：所有节点只有左子节点，最长路径为1。
• 交替路径：如 1→2→3→4→5，路径长度为4。

2. 多语言实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def longestZigZag(self, root: TreeNode) -> int:
        self.max_len = 0
        
        def 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 0
            current_right = right_left + 1 if node.right else 0
            self.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. 工程优化

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