二叉树最大路径和问题
作者: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);
}
}