687. Longest Univalue Path

2023-12-21 16:18
文章标签 path longest 687 univalue

本文主要是介绍687. Longest Univalue Path,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

687. 最长同值路径

给定一个二叉树,找到最长的路径,这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意:两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

              5/ \4   5/ \   \1   1   5

输出:

2

示例 2:

输入:

              1/ \4   5/ \   \4   4   5

输出:

2

注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

解法一

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int find(TreeNode* root) {if(!root) return 0;int pl = find(root->left);int pr = find(root->right);int count = 0, pathLen = 0;if(root->left && root->right) {int vl = root->left->val, vr = root->right->val, vm = root->val;count = max(vl == vm ? pl + 1 : 0, vr == vm ? pr + 1 : 0);if(vl == vm && vl == vr) pathLen = pl + pr + 2;}else if(root->left && !root->right) {count = root->left->val == root->val ? pl + 1 : 0;}else if(!root->left && root->right) {count = root->right->val == root->val ? pr + 1 : 0;}res = max(res, max(count, pathLen));return count;}int longestUnivaluePath(TreeNode* root) {res = 0;find(root);return res;}
private:int res;
};

思路:

此题解法和之前求树高的题目类似,只不过不再是单纯地对树高求和,中间要加一些条件,需要满足条件的父子结点才能计数。

函数find(root)采用先序遍历,返回值count是从当前根结点root出发的最长同值路径长。所以在遍历过程中有几种情况:

  1. 当前根结点root的左、右子树都为空。此时count为0;
  2. 左、右子树有其一为空。此时可分两种情况:
① 非空子结点值等于根结点值。此时count为find(root->left) + 1;
② 非空子结点值不等于根结点值。此时count为0;
  1. 左、右子树都非空。此时可分3种情况:
①左子结点值右子结点值都等于根结点值,此时count为 1 + max(find(root->left), find(root->right));
②左、右子结点值有其一等于根结点值,此时count为 1 + find(子结点值等于根结点值的那个子树);
③左、右子结点值都不等于根结点值,此时count为0。

以上的find函数只是返回了从根结点出发的最长同值路径长,而题目要求路径不一定要以根结点为出发点(就是说可以穿过根结点),所以需要一个变量pathLen,计录遍历过程中穿过当前根结点的最长同值路径长。

还好这一改动并不复杂,第1、2种情况(左、右子树至少有一个为空)里,pathLen都等于count。

对于第3种情况(左、右子树都非空),在其分类②、③中,pathLen也直接等于count。在分类①中,需要使pathLen等于左、右子树的最长同值路径长之和再加2,也就是pathLen = find(root->left) + find(root->rigfht) + 2。

使用res记录pathLen出现过的最大值即可。

思路理顺很好理解,就是条件太多,代码不好看。

2019/06/20 23:36

这篇关于687. Longest Univalue Path的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/520656

相关文章

leetcode#32. Longest Valid Parentheses

题目 Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", wh

Flask 创建app 时候传入的 static_folder 和 static_url_path参数理解

Flask 在创建app的时候 是用 app = Flask(__name__) 来创建的,不传入 static_folder参数的话 ,默认的静态文件的位置是在 static目录下 我们可以进入 Flask的源码里面查看 ctrl+鼠标左键进入 这是Flask的 __init__源码(后面还有一些,我就选了需要的代码)     def __init__(self,import_

(4)SVG-path中的椭圆弧A(绝对)或a(相对)

1、概念 表示经过起始点(即上一条命令的结束点),到结束点之间画一段椭圆弧 2、7个参数 rx,ry,x-axis-rotation,large-arc-flag,sweep-flag,x,y (1)和(2)rx,ry rx:椭圆的x轴半径(即水平半径) ry:椭圆的y轴半径(即垂直半径) 这两个参数好理解,就是椭圆的两条对称轴半径,相等即为圆 也可以写比例,写比例时默认用符合条件

【ArcGIS Pro实操第二期】最小成本路径(Least-cost path)原理及实操案例

ArcGIS Pro实操第一期:最小成本路径原理及实操案例 概述(Creating the least-cost path)1.1 原理介绍1.2 实现步骤1.3 应用案例 2 GIS实操2.1 工具箱简介2.1.1 成本路径(Cost path)2.1.2 成本距离(Cost distance)2.1.2 路径距离(Path Distance) 2.2 案例: 参考 概述(Cre

大数据Java基础-JAVA IO 9】java IO流 (九) Path、Paths、Files的使用

1.NIO的使用说明: >Java NIO (New IO,Non-Blocking IO)是从Java 1.4版本开始引入的一套新的IO API,可以替代标准的Java IO AP。 >NIO与原来的IO同样的作用和目的,但是使用的方式完全不同,NIO支持面向缓冲区的(IO是面向流的)、基于通道的IO操作。 >NIO将以更加高效的方式进行文件的读写操作。 >随着 JDK 7 的发布,Java对N

java常用算法之最长回文子串(Longest Palindromic Substring)

方法一:时间复杂度为O(n^3) public static String longestPalindrome1(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i

最短路径(Shortest Path)

单源最短路径问题 Dijkstra算法:基于递推的思想设计 未达顶点的最短路径一定是由已到达顶点的最短路径求出 所有顶点之间的最短路径,任意两个顶点之间的最短路径 Floyd算法:只是Dijkstra最短路径算法的加强,其本质还是递推

【ArcGIS Pro实操第一期】最小成本路径(Least-cost path)原理及实操案例

ArcGIS Pro实操第一期:最小成本路径原理及实操案例 概述(Creating the least-cost path)1.1 原理介绍1.2 实现步骤1.3 应用案例 2 GIS实操2.1 工具箱简介2.1.1 成本路径(Cost path)2.1.2 成本距离(Cost distance)2.1.2 路径距离(Path Distance) 2.2 案例: 参考 概述(Cre

[LeetCode] 300. Longest Increasing Subsequence

题:https://leetcode.com/problems/longest-increasing-subsequence/description/ 题目 Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7

[LeetCode] 64. Minimum Path Sum

题:https://leetcode.com/problems/minimum-path-sum/description/ 题目 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers