LWC 52:687. Longest Univalue Path

LWC 52:687. Longest Univalue Path

传送门:687. Longest Univalue Path

Problem:

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.

Note:

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.

思路: 此题的trick在于如何划分子问题,首先对于原问题的划分如下:

如果最长path经过根节点,则计算出来

否则,分别从左子树和右子树中找出最长路径(不经过根节点)

接下来,只需要计算从某个根结点出发,分别链接左子树的最大路径长度和右子树的最大路径长度。

此处的原问题划分如下:

计算左子树的最大长度

计算右子树的最大长度

如果左右子树根节点的val和它们的父结点val相同,则取其中长度最大的。

代码如下:

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) return 0;
        int val = root.val;
        int res = 0;
        if (root.left != null && root.left.val == val) {
            res = 1 + dfs(root.left);
        }
        if (root.right != null && root.right.val == val) {
            res += 1 + dfs(root.right);
        }
        return Math.max(res, Math.max(longestUnivaluePath(root.left), longestUnivaluePath(root.right)));
    }

    public int dfs(TreeNode root) {
        if (root == null) return 0;
        int res = 0;
        int val = root.val;

        if (root.left != null && root.left.val == val) {
            res = 1 + dfs(root.left);
        }

        if (root.right != null && root.right.val == val) {
            res = Math.max(res, 1 + dfs(root.right));
        }
        return res;
    }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老马说编程

(43) 剖析TreeMap / 计算机程序的思维逻辑

40节介绍了HashMap,我们提到,HashMap有一个重要局限,键值对之间没有特定的顺序,我们还提到,Map接口有另一个重要的实现类TreeMap,在Tre...

2128
来自专栏java学习

面试题18(以下关于集合类 ArrayList 、 LinkedList 、 HashMap 描述错误的是?)

以下关于集合类 ArrayList 、 LinkedList 、 HashMap 描述错误的是? A)HashMap实现Map接口,它允许任何类型的键和值对象,...

3025
来自专栏刘君君

JDK8的ArrayList源码学习笔记

2887
来自专栏芋道源码1024

Jedis 对 Redis 的操作详解

本篇主要阐述Jedis对redis的五大类型的操作:字符串、列表、散列、集合、有序集合。

1903
来自专栏Java帮帮-微信公众号-技术文章全总结

14(02)正则表达式,Pattern,Mactcher,Math,BigInteger,BigDeximal,System等

5:BigInteger(理解) (1)针对大整数的运算 (2)构造方法 A:BigInteger(String s) package cn.itcas...

3707
来自专栏文武兼修ing——机器学习与IC设计

二叉查找树二叉查找树

二叉查找树 二叉查找树是一种特殊的二叉树,该数据结构的核心性质是: 对于树中的每个节点X,它的左子树中所有关键字值小于X的关键字值,而它的右子树中所有关键字值...

30311
来自专栏IT可乐

JDK1.8源码(五)——java.util.ArrayList 类

  关于 JDK 的集合类的整体介绍可以看这张图,本篇博客我们不系统的介绍整个集合的构造,重点是介绍 ArrayList 类是如何实现的。 1、ArrayLis...

41411
来自专栏向治洪

数据结构之线性表

基本概念 线性表(List):由零个或多个数据元素组成的有限序列。 特征: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无...

2089
来自专栏互扯程序

Java集合深度解析之ArrayList

KS Knowledge Sharing 知识分享 现在是资源共享的时代,同样也是知识分享的时代,如果你觉得本文能学到知识,请把知识与别人分享。 转自:...

2196
来自专栏weixuqin 的专栏

数据结构学习笔记(线性表)

3085

扫码关注云+社区

领取腾讯云代金券