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

题目描述
给定一棵二叉树的根节点 root，你需要找到树中最长同值路径的长度。该路径中每个节点的值都相同，且路径不一定经过根节点。路径的长度由路径中的边数（即节点数减1）表示。例如，路径 [5,5,5] 的长度为 2。

解题思路
该问题本质是求二叉树中值相同的节点构成的最长链（路径）。由于路径可能不经过根节点，需要递归遍历每个节点，计算以当前节点为最高点的同值路径长度，并更新全局最大值。关键点在于：

1. 定义递归函数 dfs(node)，返回以 node 为起点的单向同值路径最大长度（向下延伸）。
2. 在递归过程中，比较左右子树与当前节点值是否相同，若相同则连接路径。
3. 路径可能分叉（左右子树均连接），但返回时只能选择一侧（因为路径是单向的）。

步骤详解

1. 定义状态与递归函数

   • 设全局变量 max_len 记录最长同值路径长度。
   • 定义 dfs(node)：返回以 node 为起点，向下延伸的同值路径最大边数（即节点数减1）。

2. 递归终止条件

   • 若 node 为空，返回 0。

3. 递归左右子树

   • 计算左子树返回值 left = dfs(node.left)。
   • 计算右子树返回值 right = dfs(node.right)。

4. 判断同值连接

   • 初始化当前左右路径长度 left_path = 0，right_path = 0。
   • 若 node.left 存在且 node.left.val == node.val，则 left_path = left + 1（连接左子树路径）。
   • 若 node.right 存在且 node.right.val == node.val，则 right_path = right + 1（连接右子树路径）。

5. 更新全局最大值

   • 当前节点为最高点的路径长度 = left_path + right_path（路径可经过左右子树）。
   • 更新 max_len = max(max_len, left_path + right_path)。

6. 返回单侧最大长度

   • 返回 max(left_path, right_path)，因为向上返回时路径只能是单向的。

7. 初始化与调用

   • 初始化 max_len = 0，调用 dfs(root)，最终返回 max_len。

示例分析
以二叉树 [1,4,5,4,4,5] 为例：

        1
       / \
      4   5
     / \   \
    4   4   5

• 叶子节点（如值为4的节点）返回0。
• 中间节点（值为4的节点）连接左右同值子节点，路径长度为2（左-中-右），但返回时只返回1（单侧最大）。
• 根节点1无双侧同值连接，不影响最大值。
• 最终最长路径为值为4的节点构成的路径（长度为2）。

复杂度分析

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

关键点总结

• 路径可能不经过根节点，需在递归过程中更新全局最大值。
• 返回值为单侧路径长度，但更新最大值时可合并双侧路径。
• 注意路径长度定义为边数（节点数减1），与题目要求一致。