『LeetCode』687 最长同值路径

题目

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

相似题目

题解

【最长同值路径】二叉树的递归应用

递归

给定一棵二叉树，最长同值路径只有两种情况：

路径经过根节点，需计算左子树部分和右子树部分与根节点同值的最长路径
路径不经过根节点，路径在左子树或者右子树

以此不难想到使用递归处理，对于第二种情况直接递归处理即可，我们只需在递归中处理第一种情况

定义 dfs(root, val) 返回以 root 为根节点的与 val 同值的最长路径，而对于经过 root 而不经过其父节点的最长路径我们使用一个全局的变量进行记录。

注意我们代码中统计的是路径中的结点数量而题目要求的是边数所以结果是结点数量-1

# Code language: Python
class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        ans = 0

        def dfs(root, val=-1):
            if not root: return 0
            left, right = dfs(root.left, root.val), dfs(root.right, root.val)
            nonlocal ans
            ans = max(ans, left + right)
            return max(left, right) + 1 if root.val == val else 0
        
        dfs(root)
        return ans

// Code language: Java
class Solution {
    int ans;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root, -1);
        return ans;
    }

    public int dfs(TreeNode root, int val) {
        if (root == null) return 0;
        int left = dfs(root.left, root.val), right = dfs(root.right, root.val);
        ans = Math.max(ans, left + right);
        return root.val == val ? Math.max(left, right) + 1 : 0;
    }
}

// Code language: C++
class Solution {
public:
    int ans = 0;
    int longestUnivaluePath(TreeNode* root) {
        dfs(root, -1);
        return ans;
    }

    int dfs(TreeNode* root, int val) {
        if (root == nullptr) return 0;
        int left = dfs(root->left, root->val), right = dfs(root->right, root->val);
        ans = max(ans, left + right);
        return root->val == val ? max(left, right) + 1 : 0;
    }
};

/* Code language: JavaScript */
var longestUnivaluePath = function(root) {
    let ans = 0;
    const dfs = function(root, val) {
        if (root == undefined) return 0;
        const left = dfs(root.left, root.val), right = dfs(root.right, root.val);
        ans = Math.max(ans, left + right);
        return root.val == val ? Math.max(left, right) + 1 : 0;
    };
    dfs(root, -1);
    return ans;
};

时间复杂度: \(O(n)\)
空间复杂度: 递归栈需要 \(O(n)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』687 最长同值路径

题目

标签

相似题目

题解

递归