LeetCode 0-200 题解
Opened this issue · 1 comments
thyecust commented
Done：
- 124，二叉树中的最大路径和，Hard
thyecust commented
124，二叉树中的最大路径和
给一棵非空二叉树，定义路径：从树上的一个结点出发，到达任意一个结点的序列，至少经过一个结点，可以不经过根结点。
求这棵树的最大路径和。
如
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
首先考虑，以A结点为根节点的子树，在这个子树上，以A结点为起点的路径，要么只有A，要么从A走向左子结点，要么从A走向右子结点。
那么在这个子树上，以A为起点的路径最大值就是
f(-10) = max(-10, -10+f(9), -10+f(20))
f(9) = 9
f(20) = max(20, 20+f(15), 20+f(7))
f(15) = 15
f(7) = 7
f(20) = max(20, 20+f(15), 20+f(7)) = max(20, 35, 7) = 35
f(-10) = max(-10, -10+f(9), -10+f(20)) = max(-10, -1, 25) = 25
如果要考虑整棵树上的最大路径和，我们需要一个全局变量maxSum，初始化为无穷小，对树上的每一个结点r，当 r.val+f(r.left)+f(r.right) > maxSum 的时候就更新它。
时间复杂度和空间复杂度都是O(N)。
C++：
class Solution {
private:
int maxSum = INT_MIN;
public:
int maxGain(TreeNode* node) {
if (node == nullptr) {
return 0;
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时，才会选取对应子节点
int leftGain = max(maxGain(node->left), 0);
int rightGain = max(maxGain(node->right), 0);
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
int priceNewpath = node->val + leftGain + rightGain;
// 更新答案
maxSum = max(maxSum, priceNewpath);
// 返回节点的最大贡献值
return node->val + max(leftGain, rightGain);
}
int maxPathSum(TreeNode* root) {
maxGain(root);
return maxSum;
}
};
Python：
class Solution:
def __init__(self):
self.maxSum = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def maxGain(node):
if not node:
return 0
# 递归计算左右子节点的最大贡献值
# 只有在最大贡献值大于 0 时，才会选取对应子节点
leftGain = max(maxGain(node.left), 0)
rightGain = max(maxGain(node.right), 0)
# 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
priceNewpath = node.val + leftGain + rightGain
# 更新答案
self.maxSum = max(self.maxSum, priceNewpath)
# 返回节点的最大贡献值
return node.val + max(leftGain, rightGain)
maxGain(root)
return self.maxSum