LC 687. 最长同值路径

题目描述

这是 LeetCode 上的 687. 最长同值路径 ，难度为 中等。

给定一个二叉树的 root，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。

两个节点之间的路径长度 由它们之间的边数表示。

示例 1:

输入：root = [5,4,5,1,1,5]

输出：2

示例 2:

输入：root = [1,4,5,4,4,5]

输出：2

提示:

• 树的节点数的范围是 $[0, 10^4] $
• $-1000 <= Node.val <= 1000$
• 树的深度将不超过 1000

---

递归

设计递归函数 int dfs(TreeNode root)，含义为传入根节点 root，返回以该节点为起点，往下走同值路径所能经过的最大路径长度（即不能同时往左右节点走），同时使用全局变量 max 记录答案路径所能经过最大路径长度。

在递归函数内部，先通过递归 root 的左右子节点，拿到以 root.left 和 root.right 为起点的最大路径长度 l 和 r，然后根据当前节点值和左右子节点值的相等关系来更新 ans，同时用 cur 维护「以当前节点 root 为目标路径中深度最小（位置最高）节点时」所经过的最大路径长度。

Java 代码：

class Solution {
    int max = 0;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return max;
    }
    int dfs(TreeNode root) {
        if (root == null) return 0;
        int ans = 0, cur = 0, l = dfs(root.left), r = dfs(root.right);
        if (root.left != null && root.left.val == root.val) {
            ans = l + 1; cur += l + 1;
        }
        if (root.right != null && root.right.val == root.val) {
            ans = Math.max(ans, r + 1); cur += r + 1;
        }
        max = Math.max(max, cur);
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int maxv = 0;
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        int ans = 0, cur = 0;
        int l = dfs(root->left), r = dfs(root->right);
        if (root->left != nullptr && root->left->val == root->val) {
            ans = l + 1; cur += l + 1;
        }
        if (root->right != nullptr && root->right->val == root->val) {
            ans = max(ans, r + 1); cur += r + 1;
        }
        maxv = max(maxv, cur);
        return ans;
    }
    int longestUnivaluePath(TreeNode* root) {
        dfs(root);
        return maxv;
    }
};

Python 代码：

class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        maxv = 0
        def dfs(root):
            nonlocal maxv
            if not root: return 0
            ans, cur = 0, 0
            l, r = dfs(root.left), dfs(root.right)
            if root.left and root.left.val == root.val:
                ans = l + 1
                cur += l + 1
            if root.right and root.right.val == root.val:
                ans = max(ans, r + 1)
                cur += r + 1
            maxv = max(maxv, cur)
            return ans
        dfs(root)
        return maxv

TypeScript 代码：

let max = 0;
function longestUnivaluePath(root: TreeNode | null): number {
    max = 0
    dfs(root)
    return max
};
function dfs(root: TreeNode | null): number {
    if (root == null) return 0
    let ans = 0, cur = 0, l = dfs(root.left), r = dfs(root.right)
    if (root.left != null && root.left.val == root.val) {
        ans = l + 1; cur += l + 1
    }
    if (root.right != null && root.right.val == root.val) {
        ans = Math.max(ans, r + 1); cur += r + 1
    }
    max = Math.max(max, cur)
    return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：忽略递归带来的额外空间开销，复杂度为 $O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.687 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。