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

我将为你详细讲解"最长同值路径问题"，这是一个在二叉树中应用区间动态规划思想的经典问题。

问题描述

给定一棵二叉树的根节点，找到最长的路径长度，其中路径上的所有节点具有相同的值。这条路径可以经过根节点，也可以不经过根节点。路径长度用路径上的边数表示。

例如：

      5
     / \
    4   5
   / \   \
  1   1   5

最长同值路径是3（从右子树的5-5-5）

核心思路分析

这个问题看似是树的问题，但实际上可以用类似区间DP的思想来解决。我们需要自底向上地计算每个节点的信息，然后组合这些信息来得到全局最优解。

解题步骤详解

步骤1：定义状态

对于每个节点，我们需要维护两个关键信息：

• 从该节点向下的最长同值路径长度
• 经过该节点的最长同值路径长度

定义递归函数：

def dfs(node):
    # 返回 (当前节点向下的最长同值路径长度, 经过当前节点的最长同值路径长度)

步骤2：递归终止条件

如果节点为空，返回(0, 0)

步骤3：递归计算左右子树

对于当前节点：

1. 递归计算左子树的结果：(left_down, left_through)
2. 递归计算右子树的结果：(right_down, right_through)

步骤4：计算当前节点的结果

向下最长路径计算：

• 如果左子节点存在且值与当前节点相同：left_path = left_down + 1
• 否则：left_path = 0
• 如果右子节点存在且值与当前节点相同：right_path = right_down + 1
• 否则：right_path = 0

当前节点向下的最长路径：max(left_path, right_path)

经过当前节点的最长路径：

• 如果左右子节点都与当前节点同值：through_current = left_path + right_path
• 如果只有左子节点同值：through_current = left_path
• 如果只有右子节点同值：through_current = right_path
• 否则：through_current = 0

当前节点的最长路径：max(through_current, left_through, right_through)

步骤5：完整算法实现

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

def longestUnivaluePath(root):
    def dfs(node):
        if not node:
            return 0, 0
        
        # 递归计算左右子树
        left_down, left_max = dfs(node.left)
        right_down, right_max = dfs(node.right)
        
        # 计算当前节点向下的最长路径
        left_path = 0
        right_path = 0
        
        if node.left and node.left.val == node.val:
            left_path = left_down + 1
        if node.right and node.right.val == node.val:
            right_path = right_down + 1
        
        current_down = max(left_path, right_path)
        
        # 计算经过当前节点的最长路径
        through_current = left_path + right_path
        current_max = max(through_current, left_max, right_max)
        
        return current_down, current_max
    
    _, result = dfs(root)
    return result

详细示例分析

让我们用前面的例子来逐步分析：

      5
     / \
    4   5
   / \   \
  1   1   5

步骤分析：

1. 叶子节点1（最左）：

   • 向下路径：0（没有子节点）
   • 经过路径：0
   • 返回：(0, 0)

2. 叶子节点1（中间）：

   • 向下路径：0
   • 经过路径：0
   • 返回：(0, 0)

3. 节点4：

   • 左子节点1：值不同，贡献0
   • 右子节点1：值不同，贡献0
   • 向下路径：0
   • 经过路径：0
   • 返回：(0, 0)

4. 叶子节点5（最右）：

   • 向下路径：0
   • 经过路径：0
   • 返回：(0, 0)

5. 节点5（中间右）：

   • 左子节点：无
   • 右子节点5：值相同，贡献1
   • 向下路径：1
   • 经过路径：1
   • 返回：(1, 1)

6. 根节点5：

   • 左子节点4：值不同，贡献0
   • 右子节点5：值相同，贡献2（1+1）
   • 向下路径：2
   • 经过路径：2（左0 + 右2）
   • 全局最大值：max(2, 左子树最大值0, 右子树最大值1) = 2

最终结果是3？等等，我们漏掉了什么...

修正算法

我发现了问题！在计算经过当前节点的路径时，我们需要考虑左右两边的情况。让我修正算法：

def longestUnivaluePath(root):
    self.max_length = 0
    
    def dfs(node):
        if not node:
            return 0
        
        left_length = dfs(node.left)
        right_length = dfs(node.right)
        
        # 计算左右路径长度
        left_arrow = right_arrow = 0
        
        if node.left and node.left.val == node.val:
            left_arrow = left_length + 1
        if node.right and node.right.val == node.val:
            right_arrow = right_length + 1
        
        # 更新全局最大值
        self.max_length = max(self.max_length, left_arrow + right_arrow)
        
        # 返回当前节点向下的最长路径
        return max(left_arrow, right_arrow)
    
    dfs(root)
    return self.max_length

修正后的详细分析

重新分析示例：

      5
     / \
    4   5
   / \   \
  1   1   5

1. 叶子节点1：返回0

2. 叶子节点1：返回0

3. 节点4：

   • 左右子节点值不同，left_arrow=0, right_arrow=0
   • 返回max(0,0)=0

4. 叶子节点5：返回0

5. 节点5（中间右）：

   • 右子节点值相同，right_arrow=1
   • 更新max_length=max(0, 0+1)=1
   • 返回1

6. 根节点5：

   • 左子节点值不同，left_arrow=0
   • 右子节点值相同，right_arrow=2（1+1）
   • 更新max_length=max(1, 0+2)=2

等等，还是2？让我再仔细检查...

最终正确的分析

实际上，最长路径应该是3（节点5-5-5）。问题在于我们计算的是边数，而路径上有3个节点，所以边数是2。

让我用正确的例子：

      5
     / \
    4   5
   / \   \
  1   1   5

最长路径是：右子树的5 → 右子树的5 → 叶子节点的5，路径长度为2（边数）。

如果例子改为：

      1
     / \
    4   5
   / \   \
  4   4   5

最长路径是2（左子树的4-4-4）。

关键要点总结

1. 自底向上计算：从叶子节点开始，逐步向上计算每个节点的信息
2. 状态定义：每个节点返回从该节点向下的最长同值路径长度
3. 路径组合：经过当前节点的最长路径是左右路径之和
4. 全局维护：使用全局变量记录遇到的最大值

这个问题的核心思想是将大问题分解为子问题，这正是区间动态规划的精髓所在，只是在树结构上的应用。