Java实现 LeetCode 124 二叉树中的最大路径和
2024-08-27 20:29:07
124. 二叉树中的最大路径和
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
PS:
对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况:
1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径
2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径
class Solution {
private int ret = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
getMax(root);
return ret;
}
private int getMax(TreeNode r) {
if(r == null) return 0;
int left = Math.max(0, getMax(r.left)); // 如果子树路径和为负则应当置0表示最大路径不包含子树
int right = Math.max(0, getMax(r.right));
ret = Math.max(ret, r.val + left + right); // 判断在该节点包含左右子树的路径和是否大于当前最大路径和
return Math.max(left, right) + r.val;
}
}
最新文章
- 转:OSGi 入门篇:生命周期层
- Elasticsearch聚合 之 Date Histogram聚合
- MPI+WIN10并行试运行
- 循环语句for
- Oracle VM VirtualBox 安装笔记
- Android 之 悬浮窗
- HBase学习——4.HBase过滤器
- snmp简单测试
- iSlide——图标库、图示库的用法
- js 常用正则表达式
- spring mvc后端校验validator
- [C++]String::find
- 关于使用AzureCli登陆提示SSLError的错误解决方案
- redis和memcached相关
- codeforces 293E Close Vertices
- JavaWeb总结(一)
- 实现linux下的ls
- python webdriver 测试框架-数据驱动xml驱动方式
- Java中的内部类(二)成员内部类
- [置顶]
 C语言中 || 和 &&
热门文章
- Offset等一些类似属性的使用
- [ACdream 1212 New Year Bonus Grant]贪心
- js日期格式与时间戳相互转换
- Rasa init报错:AttributeError: type object 'Callable' has no attribute '_abc_registry'
- Linux系统如何安装qt-desinger
- MyBatis入门知识汇总
- Mysql添加更新删除数据-表
- springmvc数据处理-中文乱码
- MySQL复制表结构以及复制表等等
- python的生成器和迭代器