节点之和最大的路径
# 📃 题目描述
题目链接:
- 剑指 Offer II 051. 节点之和最大的路径 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 124. 二叉树中的最大路径和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
# 🔔 解题思路
主要就是抓住一个点:如果某个节点作为路径的起点,那么就不能同时走到它的左右孩子,只能走其中一边
这里注意区分下某个节点的贡献值(以该节点为【起点】的最大路径和)和最大路径和(以该节点为【拐点】的最大路径和)的概念
比如:
1
/ \
2 3
节点 1 的贡献值(以 1 为起点的最大路径和)是1 + Math.max(1 的左孩子为起点的最大路径和(1 的左孩子的贡献值),以 1 的右孩子为起点的最大路径和(1 的右孩子的贡献值))= 1, + Math.max(2,3) = 4
而以 1 为拐点的最大路径和是 以 1 的左孩子为起点的最大路径和(1 的左孩子的贡献值) + 1 + 以 1 的右孩子为起点的最大路径和(1 的右孩子的贡献值)
我们的目的就是,找到路径和最大的那个拐点
所以,典型的后序遍历
class Solution {
// 存储最大路径和
private int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
// 经过当前节点 root 并前往其左子树或右子树的路径的节点值之和的最大值
maxGain(root);
return maxSum;
}
// 返回 cur 的贡献值(以 cur 为起点的最大路径和)
private int maxGain(TreeNode cur) {
if (root == null) {
return 0;
}
// 这一段 corner case 可以不写
// if (cur.left == null && cur.right == null) {
// res = Math.max(res, cur.val);
// return cur.val;
// }
// 以 cur.left 为起点的路径和最大值
// 注意这里不要和 Integer.MIN_VALUE 比较,因为负数也 > MIN_VALUE,但是负数显然对最大路径和没有帮助
// 所以,只有在最大贡献值大于 0 时,才会选取对应子节点
int leftGain = Math.max(0, maxGain(cur.left));
// 以 cur.right 为起点的路径和最大值
int rightGain = Math.max(0, maxGain(cur.right));
// 以 cur 为拐点的路径和
int sum = leftGain + cur.val + rightGain;
// 最大路径和
maxSum = Math.max(maxSum, sum);
// 返回 cur 的贡献值(以 cur 为起点的最大路径和)
return cur.val + Math.max(leftGain, rightGain);
}
}
# 💥 复杂度分析
- 空间复杂度:O(LogN),取决于树的高度
- 时间复杂度:O(N),对每个节点访问不超过 2 次
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10