统计同值子树路径的最大长度

问题描述
给定一棵二叉树的根节点 root，定义一条同值路径为：路径上所有节点的值都相同。路径可以不从根节点开始，也不一定在叶子节点结束，但必须沿着父子连接方向（即路径必须是直的，不能分叉）。请你找到这棵树中最长的同值路径的长度。

例如，对于二叉树：

      5
     / \
    4   5
   / \   \
  1   1   5

最长同值路径是路径 5 -> 5 -> 5（从右子树的两个5连接到根节点的5），长度为3（路径上的节点数为3，路径长度通常定义为节点数减1，这里我们按节点数计算，但注意题目有时定义可能不同，我们按常见变体“节点数”来讲解，最终可灵活转换）。

解题思路
这是一个树形动态规划问题，但本质上仍是“线性”的，因为我们在递归遍历树的过程中，对每个节点只需维护一个状态，并利用子节点的状态更新当前节点状态，最终得到全局最优。

我们可以定义：

• 对于任意节点 node，我们计算以 node 为起点，向下延伸的单侧最长同值路径长度（即只能沿着左或右一个方向向下走）。
• 同时，在计算过程中，我们可以更新全局答案：考虑经过 node 的路径，它可以同时向左和向右延伸，形成一个“倒V”形状的路径。

步骤拆解

1. 状态定义
   设 dfs(node) 返回一个值，表示以 node 为起点，向下延伸的单侧最长同值路径的节点数（包括 node 自己）。
   注意：这条路径必须所有节点值都与 node.val 相同，并且只能沿着一个分支（左或右）向下。

2. 递归计算
   对当前节点 node：

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

   注意：left 和 right 是假设左/右子节点值与 node 相同时才能延续，否则必须断开（长度为0）。
   具体来说：

   • 如果 node.left 存在且 node.left.val == node.val，则左侧可以延续，当前节点单侧路径可以考虑左分支，长度为 left_len = left。
   • 否则 left_len = 0。
   • 同理，右侧得到 right_len。

3. 更新全局答案
   经过 node 的最长同值路径的节点数 = left_len + 1 + right_len。
   这里 +1 是 node 自己。
   用这个值更新全局最大长度 max_len。

4. 返回值
   dfs(node) 返回的是单侧最长，所以只能选择左或右的一个方向，即返回 1 + max(left_len, right_len)。

5. 初始化
   全局变量 max_len 初始为 0（至少一个节点时长度为1）。

6. 递归边界
   如果 node 为空，返回 0。

例子详解
用之前的例子：

      5
     / \
    4   5
   / \   \
  1   1   5

递归过程：

• 节点1（左叶）：左右为空，返回1，经过它的路径节点数=1，更新 max_len=1。
• 节点1（右叶）：同理，返回1。
• 节点4：左子值1≠4，所以 left_len=0；右子值1≠4，right_len=0。返回值=1，经过它的路径节点数=1。
• 节点5（叶，在右下）：左右为空，返回1。
• 节点5（根右子）：左空，右子值5==5，所以 right_len=dfs(右子5)=1，返回值=1+1=2。经过它的路径节点数= left_len(0) +1 + right_len(1) = 2，更新 max_len=2。
• 根节点5：左子值4≠5，left_len=0；右子值5==5，right_len=dfs(右子5)=2。返回值=1+max(0,2)=3。经过它的路径节点数=0+1+2=3，更新 max_len=3。

最终 max_len=3。

复杂度分析

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

代码框架（Python）

def longestUnivaluePath(root):
    max_len = 0
    
    def dfs(node):
        nonlocal max_len
        if not node:
            return 0
        left_len = dfs(node.left)
        right_len = dfs(node.right)
        
        # 如果子节点与当前节点值相同，才能延续路径
        left_arrow = right_arrow = 0
        if node.left and node.left.val == node.val:
            left_arrow = left_len
        if node.right and node.right.val == node.val:
            right_arrow = right_len
        
        # 更新经过当前节点的最长路径
        max_len = max(max_len, left_arrow + 1 + right_arrow)
        
        # 返回单侧最长
        return 1 + max(left_arrow, right_arrow)
    
    dfs(root)
    return max_len

关键点

• 区分“单侧延伸”和“双侧路径”：返回值用于父节点延续，而更新答案时考虑左右合并。
• 只有当子节点值与当前节点值相等时才能连接。
• 本质上是一种后序遍历的动态规划，状态定义为从当前节点向下的单侧同值节点数。