树与图困难1 种解法
#124二叉树中的最大路径和
寻找二叉树中任意非空简单路径的最大节点值之和，路径不要求经过根节点。
#二叉树#深度优先搜索#后序遍历
原题
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
解题主线
- 递归返回的是能交给父节点的单边最大贡献，因此最多选择左、右子树中的一侧。
- 以当前节点为最高点的完整路径可以同时连接左右两侧，用它更新全局答案。
- 负贡献应截断为 0，但全局答案必须以最小整数初始化，才能正确处理全负树。
解法 1：后序最大贡献
后序计算左右单边贡献，先用左右贡献加当前值更新完整路径答案，再向父节点返回较大单边贡献。
-
时间复杂度： O(n)
-
空间复杂度： O(h)，h 为树高，对应递归栈
final class Solution {
static final class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public int maxPathSum(TreeNode root) {
if (root == null) throw new IllegalArgumentException("root must not be null");
int[] best = {Integer.MIN_VALUE};
maximumGain(root, best);
return best[0];
}
private int maximumGain(TreeNode node, int[] best) {
if (node == null) return 0;
// 负贡献只会降低路径和，向上合并前将其截断为 0。
int leftGain = Math.max(0, maximumGain(node.left, best));
int rightGain = Math.max(0, maximumGain(node.right, best));
// 以当前节点为最高点的完整路径可以同时连接左右两侧。
best[0] = Math.max(best[0], node.val + leftGain + rightGain);
// 交给父节点的路径不能分叉，只能选择贡献更大的一侧。
return node.val + Math.max(leftGain, rightGain);
}
}边界与易错点
- 返回给父节点时不能同时带上左右子树，否则路径会在父节点处分叉。
- 旧 res 是实例字段且不在公开方法中重置，多次调用会状态污染；整理后答案容器为方法局部变量。
- 不能把全局答案初始化为 0，因为题目要求路径非空，全负树的答案应是最大的单个节点值。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/zhard/Q124_btreeMaxPathSum.java