当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.687.Longest Univalue Path 二叉树的最长同值路径

LeetCode.687.Longest Univalue Path 二叉树的最长同值路径

题目描述

687 Longest Univalue Path
https://leetcode-cn.com/problems/longest-univalue-path/

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

              5
             / \
            4   5
           / \   \
          1   1   5
Output: 2

Example 2:

Input:

              1
             / \
            4   5
           / \   \
          4   4   5
Output: 2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.


解题过程

类似 LeetCode.543.Diameter of Binary Tree 二叉树的直径
递归计算深度,过程中更新全局变量,不同之处在于:
递归函数 depth 返回的是和根节点 root 同值的路径长度
如果root节点与左子树/右子树的值一样,长度才加一
root 与左、右子树值一样时,链接左右同值深度,形成经过root点的路径,并考虑更新全局变量。

时间复杂度 O(n),空间复杂度 O(n)

private static class SolutionV2020 {
    private int length;
    public int longestUnivaluePath(TreeNode root) {
        if (null == root) {
            return 0;
        }
        length = 0;
        depth(root);
        return length;
    }

    // 返回和根节点root同值的路径深度
    private int depth(TreeNode root) {
        if (null == root) {
            return 0;
        }
        // 左右子树中和跟同值的高度
        int left = 0, right = 0;
        if (null != root.left) {
            int d = depth(root.left);
            left = root.left.val == root.val ? d + 1 : 0;
        }
        if (null != root.right) {
            int d = depth(root.right);
            right = root.right.val == root.val ? d + 1 : 0;
        }
        // 更新最长同值路径
        length = Math.max(length, left + right);
        return Math.max(left, right);
    }
}

GitHub代码

algorithms/leetcode/leetcode/_687_LongestUnivaluePath.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_687_LongestUnivaluePath.java


上一篇 LeetCode.124.Binary Tree Maximum Path Sum 二叉树的最大路径和

下一篇 LeetCode.671.Second Minimum Node In a Binary Tree 求二叉树的次小值

阅读
评论
375
阅读预计2分钟
创建日期 2020-02-01
修改日期 2020-02-01
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论