124. 二叉树中的最大路径和
题目描述
在二叉树中，一条路径是沿着树边依次相连的节点序列，每个节点在路径中最多出现一次。路径至少含一个节点，可以从任意节点开始、在任意节点结束，不必经过根。
路径和是路径上所有节点值的总和。
输入非空二叉树的根节点 root，返回所有路径中最大的路径和。树用层序数组表示，null 代表空位。
示例 1
输入：root = [1,2,3] 输出：6
解释：路径 2 -> 1 -> 3 的和为 6。
示例 2
输入：root = [-10,9,20,null,null,15,7] 输出：42
解释：路径 15 -> 20 -> 7 的和为 42，不经过根 -10。
数据范围
- 节点总数在
[1, 3 * 10^4]之间。 -1000 <= Node.val <= 1000
解题思路
后序计算可向父节点延伸的单边最大贡献，负贡献截断为 0；当前节点可连接左右两边以更新全局答案。
为什么正确
gain 只返回一条向下分支的贡献；best 记录已处理节点作为路径最高点时的最大路径和。
复杂度分析
时间 O(n)，递归栈 O(h)；h 为树高，最坏可为 n；Python 递归受解释器递归深度限制，深链树应改用显式栈。
易错点
全负树也必须选择一个节点，best 不能初始化为 0；返回父节点时不能同时带左右两条分支。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxPathSum(self, root):
best = float('-inf')
def gain(node):
nonlocal best
if node is None:
return 0
left = max(0, gain(node.left))
right = max(0, gain(node.right))
best = max(best, node.val + left + right)
return node.val + max(left, right)
gain(root)
return bestclass Solution {
private int best;
public int maxPathSum(TreeNode root) {
best = Integer.MIN_VALUE;
gain(root);
return best;
}
private int gain(TreeNode node) {
if (node == null)
return 0;
int left = Math.max(0, gain(node.left));
int right = Math.max(0, gain(node.right));
best = Math.max(best, node.val + left + right);
return node.val + Math.max(left, right);
}
}class Solution {
public:
int maxPathSum(TreeNode* root) {
int best = INT_MIN;
function<int(TreeNode*)> gain = [&](TreeNode* node) {
if (node == nullptr)
return 0;
int left = max(0, gain(node->left));
int right = max(0, gain(node->right));
best = max(best, node->val + left + right);
return node->val + max(left, right);
};
gain(root);
return best;
}
};func maxPathSum(root *TreeNode) int {
best := math.MinInt
var gain func(node *TreeNode) int
gain = func(node *TreeNode) int {
if node == nil {
return 0
}
left := max(0, gain(node.Left))
right := max(0, gain(node.Right))
best = max(best, node.Val+left+right)
return node.Val + max(left, right)
}
gain(root)
return best
}var maxPathSum = function(root) {
let best = -Infinity;
const gain = (node) => {
if (node === null)
return 0;
const left = Math.max(0, gain(node.left));
const right = Math.max(0, gain(node.right));
best = Math.max(best, node.val + left + right);
return node.val + Math.max(left, right);
};
gain(root);
return best;
};function maxPathSum(root: TreeNode | null): number {
let best = -Infinity;
const gain = (node: TreeNode | null): number => {
if (node === null)
return 0;
const left = Math.max(0, gain(node.left));
const right = Math.max(0, gain(node.right));
best = Math.max(best, node.val + left + right);
return node.val + Math.max(left, right);
};
gain(root);
return best;
}