LeetCode687----最长同值路径
2024-09-05 07:34:23
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:
2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
思路：我们可以通过树结构发现，我们的每一个不同的同值路径（例如同值为2，或者同值为3），他们之间都是互不影响的，每次从一个同值路径跳到另一个同值路径时，前一个同值路径的状态不会影响到后一个同值路径：
当同值为4的路径走到3时，这时就应该断开4的状态，一切从0开始，直到同值为5的路径开始，于是乎上图我们又可以这样来画！
既然状态会断开，那么这里的3我们可以默认省去，这样，程序不论是走到最左下角的4节点还是最左下角的5节点，默认返回给其父节点的都是0
代码如下：
class Solution {
public int max;
public int longestUnivaluePath(TreeNode root) {
help(root);
return max;
}
public int help(TreeNode root) {
if (root == null) {
return 0;
}
int l = help(root.left);// 得到左边最大的路径
int r = help(root.right);// 得到右边最大的路径
int left = 0,right = 0;
if (root.left != null && root.val == root.left.val) {
// 证明根节点和当前的左子节点在一个路径
left=l + 1;
}
if (root.right != null && root.val == root.right.val) {
right=r + 1;
}
max = Math.max(max, left + right);
return Math.max(left, right);
}
}
最新文章
- iOS 获取当前展示的页面
- What Your Computer Does While You Wait
- C++ Prime：预处理器
- Processing.js
- ubuntu 开机进入不了图形界面
- Java 别名(Aliasing)
- Servlet做简单的ajax增删改查（分页）
- 蓝桥杯-算法训练--ALGO-6 安慰奶牛
- [E::hts_idx_push] NO_COOR reads not in a single block at the end 10 -1
- python中两种方法实现二分法查找，细致分析二分法查找算法
- 【我们一起写框架】MVVM的WPF框架（三）—数据控件
- [原创]RedisDesktopManager工具使用介绍
- Http原理与实践
- import的使用
- Linux中在线安装Mysql和修改密码设置服务启动
- springboot 以jar方式在linux后台运行
- Metal Programming Guide
- C# 中移动文件到指定位置
- border-1px；避免移动端下边框部分2px
- MariaDB数据库管理系统