LeetCode 687. 最长同值路径

约 5 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 华为 微软 美团 百度
标签
深度优先搜索 树 二叉树

题目描述

✅ 687. 最长同值路径

image-20260928235933132

image-20260928235933133

题意分析

求一条所有节点值都相同的最长路径，长度按边数计算。路径可以完全位于某棵子树中，也可以从一侧子树经过当前节点通往另一侧；它不能分叉，因此向父节点继续延伸时只能保留一条向下的分支。

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

核心思路

[!blue]

设 dfs(node) 返回从 node 出发向下走的最长同值路径边数，路径必须以 node 为一端。这个限制使返回值能接到父节点上，而子树中不经过 node 的最优路径由全局变量 ans 另外保存。

先递归处理左右孩子，再判断能否接上父子之间的边：孩子存在且值与当前节点相同，才将该孩子返回的长度加 1；否则该方向的贡献为 0。即使孩子值不同，也必须递归进入它，因为答案可能完全位于它的子树中。

令两个方向的贡献为 leftPath、rightPath。以当前节点为最高点的路径，可以将左右两段连接起来，因此用 leftPath + rightPath 更新 ans。但返回父节点时只能交出 max(leftPath, rightPath)：若把两段都带上再接父边，当前节点就会出现三个方向，形成分叉而不再是一条路径。

任意路径都有唯一的最高节点，并且至多向它的左右子树各延伸一段。遍历每个节点并尝试合并两段，就覆盖了所有可能的最长路径。空节点返回 0；叶节点两侧都不能延伸，同样返回 0，恰好符合按边数计长的要求。

解题步骤

  1. 将全局答案初始化为 0，从根节点执行后序 DFS；空节点直接返回 0。
  2. 得到两个孩子的返回值后，分别检查父子值是否相等，计算 leftPath 和 rightPath。
  3. 用两者之和更新全局答案，保留经过当前节点的完整候选。
  4. 返回两者较大值供父节点连接。遍历结束后返回全局答案，不能直接返回根节点的单边长度；空树的答案自然为 0。

代码实现

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$ 为节点数。每个节点只访问一次，合并左右返回值仅需常数时间。
  • 空间复杂度：$O(h)$，其中 $h$ 为树高，来自递归调用栈；链状树时为 $O(n)$。

关键点总结

[!green]

  • 全局候选可用两臂，递归返回只能用一臂。
  • 空节点和叶节点的可延伸边数都是零。

易错点总结

[!yellow]

  • 把两臂之和返回父节点，会构造分叉而不是路径。
  • 父子不同就直接跳过整个孩子，可能漏掉子树内部最优路径。
  • 按节点数计算，会比正确边数多一。

相似题目

题目 难度 关联与区别
543. 二叉树的直径 简单 同样在节点处组合左右最长臂，本题只有与当前节点同值的孩子臂才能接上。
549. 二叉树最长连续序列 II 中等 同样对延伸路径施加数值关系，本题要求相等，原题要求相邻差1且可连接增减两臂。
104. 二叉树的最大深度 简单 后序返回子树高度并在根处合并信息；本题仅连接值相同的向下链，该题取两侧最大高度加一。
110. 平衡二叉树 简单 后序返回子树高度并在根处合并信息；本题仅连接值相同的向下链，该题额外验证两侧高度差。
124. 二叉树中的最大路径和 困难 后序返回子树高度并在根处合并信息；本题仅连接值相同的向下链，该题舍弃负贡献后合并最大路径和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/34199933
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！