区间动态规划例题：最长同值路径问题（二叉树中的最大同值路径长度）

题目描述
给定一棵二叉树的根节点root，你需要找到这棵树中最长的同值路径的长度。这条路径要求路径上的所有节点值相同，且路径可以不经过根节点。路径长度用路径上的边数表示。

例如，对于二叉树[5,4,5,1,1,null,5]，最长的同值路径长度为2。

解题思路
虽然这是树结构问题，但可以使用类似区间DP的思想，采用后序遍历（左右根）的方式处理：

1. 定义状态：dp[node]表示以node为起点的向下同值路径的最大长度
2. 状态转移：比较node与左右子节点的值，决定是否延长同值路径
3. 全局记录：在遍历过程中记录跨越当前节点的最长同值路径

详细解题步骤

步骤1：状态定义

• 定义递归函数dfs(node)，返回以node为起点的向下同值路径最大长度
• 同时维护全局变量max_len记录整个树中的最大同值路径长度

步骤2：递归终止条件

• 如果node为空，返回0（空节点没有路径）

步骤3：递归左右子树

left_len = dfs(node.left)   # 左子树的最大同值路径长度
right_len = dfs(node.right) # 右子树的最大同值路径长度

步骤4：计算当前节点的同值路径
分两种情况考虑：

1. 与左子节点同值：如果node.left存在且node.val == node.left.val

   • 左路径长度 = left_len + 1
   • 否则左路径长度 = 0

2. 与右子节点同值：如果node.right存在且node.val == node.right.val

   • 右路径长度 = right_len + 1
   • 否则右路径长度 = 0

步骤5：更新全局最大值

• 当前节点作为"桥梁"，连接左右同值路径：
  current_len = left_path + right_path
• 更新max_len = max(max_len, current_len)

步骤6：返回以当前节点为起点的最大长度

• 返回max(left_path, right_path)给父节点

完整算法示例

def longestUnivaluePath(root):
    max_len = 0
    
    def dfs(node):
        if not node:
            return 0
            
        left = dfs(node.left)    # 左子树结果
        right = dfs(node.right)  # 右子树结果
        
        # 计算当前节点的左右路径长度
        left_path = 0
        right_path = 0
        
        if node.left and node.left.val == node.val:
            left_path = left + 1
            
        if node.right and node.right.val == node.val:
            right_path = right + 1
        
        # 更新全局最大值（当前节点作为连接点）
        nonlocal max_len
        max_len = max(max_len, left_path + right_path)
        
        # 返回以当前节点为起点的最大长度
        return max(left_path, right_path)
    
    dfs(root)
    return max_len

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(h)，递归栈深度，h为树的高度

这种解法将树形结构分解为子问题，体现了区间DP"分治+记忆"的核心思想。