LeetCode 687. 最长同值路径

2025-08-08 HGNULB 约 9 分钟

文章信息 9 个分类 4 个标签

分类

题目描述

✅ 687. 最长同值路径

题意分析

要在一棵二叉树里找一条最长的路径，路径上所有节点的值都相同，返回这条路径的长度。

有三处措辞必须逐字读。第一，长度按边数计算，不是节点数。一条只有单个节点的路径长度是 0，两个节点的路径长度是 1。第二，路径不必经过根节点，它可以完全藏在某棵子树里。第三，路径是树上的一条简单路径，可以从某个节点先往左下走一段、再折回来往右下走一段，但拐点只能有一个——一旦在某个节点向下分出两条腿，就不能在别处再分。

由此得出这题的核心张力：一条路径在它的最高点（也就是拐点）处可能是两条向下腿拼起来的，但这条拼起来的路径无法再往上延伸给父节点用，因为那会让路径在同一个节点上出现三个分支。所以「能贡献给父亲的东西」和「能作为答案的东西」是两个不同的量，必须分开算。

边界上要留心：空树（答案是 0）、单节点树（答案是 0）、整棵树所有值都相同、以及答案路径完全落在某棵子树里而根节点值与之无关的情况。

解法：后序 DFS 计算单边贡献

核心思路

暴力做法是枚举每个节点当拐点，然后从它出发分别向左右各做一次「同值向下最长延伸」的搜索。每次搜索是 $O(n)$，n 个节点各来一次，最坏 $O(n^2)$，链状树上尤其糟。

瓶颈在于「从某点向下最长同值延伸」被反复重算：算根的时候扫了整棵树，算根的孩子时又把同一批节点扫一遍。而这个量完全可以自底向上一次性攒出来。

观察到上一节说的那组张力，把两个量分开定义就一切明朗了。设 dfs(node) 返回以 node 为端点、只向下走一条腿的最长同值路径边数，记作 down(node)。它必须是单腿的，因为只有单腿才能接到父亲那条腿上继续延长。

转移是：先递归拿到 left = down(node.left) 和 right = down(node.right)。如果左孩子存在且 node.left.val == node.val，这条边可以走，左腿长度是 $left + 1$，否则左腿长度是 0；右腿同理。于是
\[down(node) = \max(leftPath,\ rightPath)\]
而全局答案在每个节点处用两条腿拼起来更新：
\[ans = \max(ans,\ leftPath + rightPath)\]
这里 leftPath + rightPath 正是「以 node 为拐点」的最长同值路径边数。因为每条同值路径都有唯一的最高点，遍历所有节点当拐点就穷尽了所有候选，不会漏也不会重。

显式的不变量是：dfs 返回值永远是单腿长度（取左右较大者），而 ans 在函数退出时已经吸收了以当前节点为拐点的双腿长度。返回单腿、更新双腿，这两件事必须严格分开——把双腿的和返回给父亲，就会拼出在树上根本不存在的分叉路径。

顺带解释一下为什么用边数不用节点数：定义成边数后，空孩子返回 0 恰好表示「零条边」，语义自洽，不需要为空节点特判成 -1 之类的怪值。

解题步骤

用一个函数级外的变量 ans 记录全局答案，初值 0。答案要跨子树比较，靠返回值是传不上来的（返回值已经被单腿语义占用了），所以必须用一个外部累积量。

递归入口先处理空节点，直接返回 0。这让「孩子不存在」自动获得零长度，后面不必单独判空来算长度。

先递归左子树得到 left，再递归右子树得到 right。必须是后序：当前节点的两条腿都依赖孩子已经算好的结果。

计算左腿：只有当 node.left != null 且 node.left.val == node.val 时才取 $left + 1$，否则取 0。判空必须写在取值前面，否则会对空指针取 val；值不相等时归零而不是继承 left，因为路径一旦断开就不能跨过去。

同样计算右腿。

用 leftPath + rightPath 更新 ans。注意这里是求和不是取最大，因为拐点处两条腿是接在一起的一条路径。

返回 max(leftPath, rightPath)。这里是取最大不是求和，因为交给父亲的必须是单腿。

最外层调用完 dfs(root) 后返回 ans，而不是返回 dfs 的结果。

以 root = [5, 4, 5, 1, 1, null, 5] 走一遍：这棵树是根 5，左孩子 4 带两个值为 1 的叶子，右孩子 5 只有一个值为 5 的右孩子。期望答案是 2。

先下到最左边的叶子 1：两个孩子递归返回 0，两个孩子都不存在所以左右腿都是 0，用 $0 + 0 = 0$ 更新 ans（仍是 0），返回 0。另一个叶子 1 完全一样。

回到节点 4：left = 0、right = 0。左孩子值是 1，与 4 不等，左腿是 0；右孩子同理是 0。用 $0 + 0 = 0$ 更新 ans，仍是 0，返回 0。

转到右子树的节点 5（记作 R）。先处理它的右孩子叶子 5：左右腿都是 0，ans 不变，返回 0。回到 R：left = 0（左孩子为空）、right = 0。左孩子不存在，左腿是 0；右孩子值是 5，与 R 的 5 相等，右腿是 $0 + 1 = 1$。用 $0 + 1 = 1$ 更新 ans，ans 变成 1。返回 $\max(0, 1) = 1$。

最后回到根 5：left = 0（来自节点 4）、right = 1（来自 R）。左孩子值是 4，与 5 不等，左腿归 0；右孩子值是 5，相等，右腿是 $right + 1 = 1 + 1 = 2$。用 $0 + 2 = 2$ 更新 ans，ans 变成 2。返回 $\max(0, 2) = 2$，但外层不用这个返回值。

最终 ans = 2，对应路径是根 5 → 右孩子 5 → 右孙子 5，三个节点两条边。

再看一个拐点不在根的用例 root = [1, 4, 5, 4, 4, null, 5]：节点 4 的两个孩子都是 4，左右腿各为 1，在它这里用 $1 + 1 = 2$ 把 ans 更新成 2，但它只把 1 返回给根；根的值是 1，与两个孩子都不同，两条腿都归 0，用 0 更新 ans 不起作用。最终答案 2，路径完全藏在左子树里，正好印证了「路径可以不经过根」。

代码实现

class Solution {
    private int ans;

    public int longestUnivaluePath(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);

        int leftPath = 0;
        if (node.left != null && node.left.val == node.val) {
            leftPath = left + 1;
        }
        int rightPath = 0;
        if (node.right != null && node.right.val == node.val) {
            rightPath = right + 1;
        }

        ans = Math.max(ans, leftPath + rightPath);
        return Math.max(leftPath, rightPath);
    }
}

func longestUnivaluePath(root *TreeNode) int {
    ans := 0
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := dfs(node.Left)
        right := dfs(node.Right)

        leftPath := 0
        if node.Left != nil && node.Left.Val == node.Val {
            leftPath = left + 1
        }
        rightPath := 0
        if node.Right != nil && node.Right.Val == node.Val {
            rightPath = right + 1
        }

        if leftPath+rightPath > ans {
            ans = leftPath + rightPath
        }
        if leftPath > rightPath {
            return leftPath
        }
        return rightPath
    }
    dfs(root)
    return ans
}

复杂度分析

时间复杂度：$O(n)$，n 是节点数。每个节点恰好进入 dfs 一次，函数体内只有两次递归调用和常数次比较、加法、取最大，没有任何重复扫描子树的动作。

空间复杂度：$O(h)$，h 是树高，全部来自递归调用栈；平衡树上是 $O(\log n)$，退化成链时是 $O(n)$。除了一个全局的 ans，没有申请任何与规模相关的额外结构。

关键点总结

树形 DP 的通用模板就是这题的形状：返回值用于向上拼接，全局变量用于收集答案，两者语义不同、算法不同（一个取 max，一个求和）。混用是这类题的头号错误。

「每条路径都有唯一最高点」是这类枚举能做到不重不漏的理论依据。想清楚这句话，就知道为什么在每个节点处只考虑「以它为拐点」是完整的枚举。

断链条件要写在「向上接一条边」这个动作上，而不是写在返回之后。值不相等时归零、而不是把孩子的长度继承下来，这一步决定了路径的连续性。

长度按边数还是按节点数，会牵动出口值、断链值和答案初值三处。开始写之前先定死口径，比写完再全局加一减一稳妥。

面试视角：这题和第 543 题（二叉树的直径）、第 124 题（最大路径和）是同一个模板的三个变体，唯一的差别是「一条边能否接上」的判定条件和聚合方式。面试时能主动点出这层关系，说明你掌握的是模板而不是单题。

面试视角：常见追问是「为什么不能直接返回左右两条腿之和」。标准回答是那条拼起来的路径在拐点已经用掉了两个分支，再往上接就会在同一个节点出现三条边，不再是简单路径。能用「简单路径」这三个字讲清楚，比说「会重复计算」准确得多。

易错点总结

错误写法：把 leftPath + rightPath 作为返回值交给父节点。用例 [4, 4, 4, 4, 4]（根 4，左孩子 4 带两个 4 叶子，右孩子 4）→ 左孩子处两条腿各为 1，错误地返回 2，根拿到后把左腿算成 3，ans 被更新成 4，而这棵树的正确答案是 3。

错误写法：返回值写成 max(left, right) + 1，不检查孩子值是否与当前节点相同。用例 [5, 4, 5, 1, 1, null, 5] → 值为 4 的节点会把两个值为 1 的孩子算进腿长，根处继续累加，ans 变成 4 而不是 2。

错误写法：判断同值时先取 node.left.val 再判空，或者只写 node.left.val == node.val。用例 [5, 4, 5, 1, 1, null, 5] → 右子树节点 R 的左孩子为空，取 val 时抛出空指针异常。

错误写法：更新答案时写成 ans = max(ans, max(leftPath, rightPath))，用取最大代替求和。用例 [1, 4, 5, 4, 4, null, 5] → 节点 4 处两条腿各为 1，取最大只得到 1，最终返回 1 而不是 2。

错误写法：最外层直接返回 dfs(root) 而不是返回 ans。用例 [1, 4, 5, 4, 4, null, 5] → 根的值是 1 与两个孩子都不同，dfs(root) 返回 0，而真实答案 2 藏在左子树里。

错误写法：按节点数计数，孩子同值时返回 left + 1 且叶子返回 1。用例 [5, 4, 5, 1, 1, null, 5] → 每条腿都多算一个节点，ans 变成 4 而不是边数口径下的 2。

错误写法：只在根节点处更新一次答案，而不是每个节点都更新。用例 [1, 4, 5, 4, 4, null, 5] → 根的两条腿都被断链归零，ans 停在 0，正确答案是 2。

错误写法：ans 初值设成 Integer.MIN_VALUE 却没有处理空树。用例 root = null → dfs 一次都不进入更新分支，函数返回 Integer.MIN_VALUE，正确答案是 0。

相似题目

题目	难度	考察点
543. 二叉树的直径	简单	同一模板去掉同值判定，任何一条边都能接，是最干净的对照组
124. 二叉树中的最大路径和	困难	聚合的是权值和且允许负数，向上贡献时要与 `0` 取最大做剪枝
1372. 二叉树中的最长交错路径	中等	向上贡献需要携带方向状态，返回值从一个数变成左右两个
LCR 051. 二叉树中的最大路径和	困难	同 124 的另一入口，适合用来复核返回单腿与更新双腿的分工