二叉树最大路径和问题
二叉树最大路径和问题
作者:Grey
原文地址:
题目描述
路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
题目链接见: LeetCode 124. Binary Tree Maximum Path Sum
主要思路
本题使用二叉树递归套路方法,相关技巧见使用二叉树的递归套路来解决的问题
定义如下数据结构
public static class Info {
// 最大路径和
public int maxPathSum;
// 头结点一直往一侧扎,能扎到的最大值是多少
public int maxPathSumFromHead;
public Info(int path, int head) {
maxPathSum = path;
maxPathSumFromHead = head;
}
}
接下来定义递归函数
Info process(TreeNode head)
递归含义表示:head 为头的二叉树,得到的 Info 信息是什么。
主函数只需要调用
public static int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
return process(root).maxPathSum;
}
即为要求的结果。
接下来就是process
方法的实现,有如下几种情况
base case ,如果head == null
,直接返回new Info(Integer.MIN_VALUE,Integer.MIN_VALUE)
,不赘述。
接下来找左右子树的信息
Info leftInfo = process(head.left);
Info rightInfo = process(head.right);
整合成以 head 为头的树的信息,
其中以 head 为头的树的maxPathSumFromHead
变量有如下几种情况
-
只包含
head.val
,这种情况暗示左右子树汇报的maxPathSumFromHead
均为负数; -
包含
head.val
和左子树的maxPathSumFromHead
,这种情况暗示右子树的maxPathSumFromHead
小于0,且左子树的maxPathSumFromHead
大于0。
以上两种情况都可以归结为
int maxPathSumFromHead =
head.val + Math.max(Math.max(leftInfo.maxPathSumFromHead, rightInfo.maxPathSumFromHead), 0);
以 head 为头的树的maxPathSum
包含如下几种情况
-
只包含
leftInfo.maxPathSum
; -
只包含
rightInfo.maxPathSum
; -
只包含
head.val + Math.max(0, leftInfo.maxPathSumFromHead) + Math.max(0, rightInfo.maxPathSumFromHead))
上述三种情况可以统一写成
int maxPathSum =
Math.max(
Math.max(leftInfo.maxPathSum, rightInfo.maxPathSum),
head.val
+ Math.max(0, leftInfo.maxPathSumFromHead)
+ Math.max(0, rightInfo.maxPathSumFromHead));
完整代码见
class Solution {
public static int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
return process(root).maxPathSum;
}
// 任何一棵树,必须汇报上来的信息
public static class Info {
public int maxPathSum;
public int maxPathSumFromHead;
public Info(int path, int head) {
maxPathSum = path;
maxPathSumFromHead = head;
}
}
public static Info process(TreeNode head) {
if (null == head) {
return new Info(Integer.MIN_VALUE, Integer.MIN_VALUE);
}
Info leftInfo = process(head.left);
Info rightInfo = process(head.right);
int maxPathSumFromHead =
head.val + Math.max(Math.max(leftInfo.maxPathSumFromHead, rightInfo.maxPathSumFromHead), 0);
int maxPathSum =
Math.max(
Math.max(leftInfo.maxPathSum, rightInfo.maxPathSum),
head.val
+ Math.max(0, leftInfo.maxPathSumFromHead)
+ Math.max(0, rightInfo.maxPathSumFromHead));
return new Info(maxPathSum, maxPathSumFromHead);
}
}
更多
相关文章
- 在springboot中,如何读取配置文件中的属性
- 一通百通,带你一次性全理解Spring 中的Template
- sqoop如何指定pg库的模式
- 关于看板方法,你需要知道的几件事
- MultipartFile与File的一些事
- 一起看看MySQL中的隐藏列
- 如何快速实现离散企业全链路数字化管理?
- 面对 Log4j2 漏洞,安全人都做了什么?
- 不会使用Spring的配置文件,赶紧把这个甩给他
- 一个BPMN流程示例带你认识项目中流程的生命周期
- Serverless,引领云计算下一个阶段
- 线程的生命周期,真的没那么简单
- APP违法使用个人信息?不用怕,华为云VSS为你保驾护航
- 带你读AI论文丨RAID2020 Cyber Threat Intelligence Modeling GCN
- Spring中部署Activiti流程定义的三种姿势
- 一起玩转玩转LiteOS组件:Opus
- 在线客服系统源码开发实战总结:gin框架模板渲染html页面
- 在线客服系统源码开发实战总结:H5 Notifications浏览器桌面通知
- wordpress独立站宝塔面板配置HTTPS教程
- 宝塔面板出现“require(): open_basedir restriction in effect. ”的解决方法