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 条评论
登录 后参与评论

相关文章

来自专栏FD的专栏

Effective Testing with RSpec 3 (英文版)(序言)

Early praise for Effective Testing with RSpec 3

1894
来自专栏技术沉淀

Ruby练习一=> {'a' => 3, 'man' => 1, 'canal' => 1, 'panama' => 1, 'plan' => 1}returns the list ["Pam", "

982
来自专栏CodingToDie

Awesome 项目

4685
来自专栏别先生

error: not found: value sqlContext/import sqlContext.implicits._/error: not found: value sqlContext

1、今天启动启动spark的spark-shell命令的时候报下面的错误,百度了很多,也没解决问题,最后想着是不是没有启动hadoop集群的问题

1180
来自专栏码匠的流水账

聊聊spring cloud的HystrixAutoConfiguration

本文主要研究一下spring cloud的HystrixAutoConfiguration

1302
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1672
来自专栏python3

openvpn linux客户端使用

内网服务器是linux的,需要连接openvpn,访问线上的应用服务。需要安装客户端,方法和服务器类似。

1582
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

3591
来自专栏IT杂记

Storm客户端提交任务失败原因分析

2860
来自专栏吴伟祥

Apache POI总结 原

Apache POI  是用Java编写的免费开源的跨平台的 Java API,Apache POI提供API给Java程式对Microsoft Office格...

881

扫码关注云+社区