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

相关文章

来自专栏来自地球男人的部落格

[LeetCode] 78. Subsets

【原题】 Given a set of distinct integers, nums, return all possible subsets. Not...

2289
来自专栏技术专栏

无向图最短路径问题

题目:无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

732
来自专栏wym

Educational Codeforces Round 44 (Rated for Div. 2)A. Chess Placing

You are given a chessboard of size 1 × n. It is guaranteed that n is even. The c...

722
来自专栏机器学习入门

LWC 63: 749. Contain Virus

Problem: A virus is spreading rapidly, and your task is to quarantine the infec...

1868
来自专栏mathor

LeetCode84.柱状图中最大的矩形

 单调栈板子题,创建一个单调递增栈(栈底到栈顶是递增的),栈内存放的数组下标,遍历数组,将下标存进栈内,以样例来说  首先栈空,0直接进栈;然后因为num...

622
来自专栏Petrichor的专栏

leetcode: 78. Subsets

541
来自专栏算法修养

PAT 1010 Radix

1010. Radix (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 St...

3355
来自专栏书山有路勤为径

链表中间段逆序

LeetCode 92. Reverse Linked List II 已知链表头节点指针head,将链表从位置m到n逆序。(不申请额外空间)

642
来自专栏desperate633

LintCode 二叉树的层次遍历 II题目代码

给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)

774
来自专栏武培轩的专栏

剑指Offer-平衡二叉树

package Tree; /** * 平衡二叉树 * 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 * 平衡二叉树(Balanced Binary ...

2727

扫码关注云+社区