最长同值路径问题（二叉树中的最大同值路径长度）

题目描述：
给定一棵二叉树的根节点 root，你需要找到这棵树中最长同值路径的长度。这条路径上的每个节点都具有相同的值。该路径不一定需要穿过根节点，但必须遵循父-子连接关系（即路径是沿着父子关系连接的，不能跳跃节点）。

解题过程：

1. 问题分析：

   • 这是一个二叉树问题，但可以使用类似区间DP的思想（树形DP）
   • 我们需要在二叉树中找到最长的路径，路径上所有节点的值都相同
   • 路径可以是任意方向（从左子树经过根节点到右子树，或者只在某个子树内部）

2. 关键思路：

   • 对于每个节点，我们计算两个值：
     • 以该节点为起点的向下最长同值路径长度
     • 经过该节点的最长同值路径长度
   • 最终答案是所有节点中经过该节点的最长同值路径长度的最大值

3. 状态定义：

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

4. 状态转移：

   • 如果节点为空，返回0
   • 递归计算左子树和右子树的结果
   • 初始化当前节点的左右路径长度都为0
   • 如果左子节点存在且值与当前节点相同，左路径长度 = 左子树结果 + 1
   • 如果右子节点存在且值与当前节点相同，右路径长度 = 右子树结果 + 1
   • 经过当前节点的路径长度 = 左路径长度 + 右路径长度
   • 更新全局最大值max_len
   • 返回max(左路径长度, 右路径长度)

5. 算法步骤：

   • 初始化max_len = 0
   • 定义递归函数dfs(node):
     • if node is null: return 0
     • left_len = dfs(node.left)
     • right_len = dfs(node.right)
     • 初始化left_path = 0, right_path = 0
     • if node.left exists and node.left.val == node.val:
       left_path = left_len + 1
     • if node.right exists and node.right.val == node.val:
       right_path = right_len + 1
     • max_len = max(max_len, left_path + right_path)
     • return max(left_path, right_path)
   • 调用dfs(root)
   • 返回max_len

6. 时间复杂度：O(n)，其中n是树中节点的个数，每个节点只被访问一次

7. 空间复杂度：O(h)，其中h是树的高度，主要是递归调用栈的空间

这个解法虽然形式上不是传统的区间DP，但运用了类似的"分治+记忆化"思想，将大问题分解为子树的小问题，是树形DP的典型应用。