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 128 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive...

1928
来自专栏赵俊的Java专栏

LeetCode 917 Reverse Only Letters

将字符串转为字符数组,用两个指针,从两端向中间走, 依次找下一个字母进行交换,直到两个指针相碰撞。

172
来自专栏算法修养

HDU 3333 Turing Tree (线段树)

Turing Tree Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768...

3388
来自专栏Bingo的深度学习杂货店

Q7 Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 1...

2684
来自专栏尾尾部落

[LeetCode]Longest Continuous Increasing Subsequence 最长连续增长序列 [LeetCode]Longest Continuous Incr

链接:https://leetcode.com/problems/longest-continuous-increasing-subsequence/descr...

501
来自专栏Bingo的深度学习杂货店

Q62 Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

922
来自专栏Petrichor的专栏

leetcode: 45. Jump Game II

1123
来自专栏Bingo的深度学习杂货店

Q101 Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric aroun...

3158
来自专栏Python小屋

Python批量设置多个Excel文件页眉页脚的源码

import os import openpyxl from openpyxl.worksheet.header_footer import _HeaderFo...

2805
来自专栏Bingo的深度学习杂货店

Q771 Jewels and Stones

You're given strings J representing the types of stones that are jewels, and S r...

2984

扫码关注云+社区