当前位置：首页 > news >正文

LeetCode 每日一题——687. 最长同值路径

news 来源：原创 2024/5/18 16:14:37

1.题目描述

687. 最长同值路径

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

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

示例 1:

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

示例 2:

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

2.解题思路与代码

2.1 解题思路

这是一道比较简单的二叉树递归遍历应用题目。要获取一颗子树相同值节点的最大路径，那么我们就可以使用递归遍历树中节点的左右子树，并返回这个节点左右子树相同节点的最大路径 left 和 right，然后将 left 和 right 相加再加上 1 （当前节点）便是以当前节点 node 为根的树相同节点的路径 path，再求出这棵树中的最大 path 便是最终结果。在遍历的同时，还需要计算以当前节点为根相同节点的左右子树的最大深度 depth。使用全局遍历 max 来记录这棵树同值路径的最大值。

2.2 代码

class Solution {
    int max = 0;

    public int longestUnivaluePath(TreeNode root) {
        process(root);
        return max;
    }

    public int process(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 记录当前节点为根的子树的同值路径
        int path = 0;
        // 记录当前节点左右子树的最长同值路径
        int depth = 0;
        int left = process(root.left);
        int right = process(root.right);
        if (root.left != null && root.val == root.left.val) {
            // 计算当前节点的左子树同值路径
            path += left + 1;
            // 计算左子树同值路径长度
            depth += left + 1;
        }
        if (root.right != null && root.val == root.right.val) {
            // 计算当前节点的左子树加右子树同值路径
            path += right + 1;
            // 计算右子树同值路径长度
            depth = Math.max(depth, right + 1);
        }
        // 计算同值路径的最大值
        max = Math.max(max, path);
        return depth;
    }
}