树与图困难1 种解法

#124二叉树中的最大路径和

寻找二叉树中任意非空简单路径的最大节点值之和，路径不要求经过根节点。

#二叉树#深度优先搜索#后序遍历

解题主线

递归返回的是能交给父节点的单边最大贡献，因此最多选择左、右子树中的一侧。

以当前节点为最高点的完整路径可以同时连接左右两侧，用它更新全局答案。

负贡献应截断为 0，但全局答案必须以最小整数初始化，才能正确处理全负树。

解法 1：后序最大贡献

后序计算左右单边贡献，先用左右贡献加当前值更新完整路径答案，再向父节点返回较大单边贡献。

时间复杂度

O(n)

空间复杂度

O(h)，h 为树高，对应递归栈

124. 二叉树中的最大路径和 · 后序最大贡献

java

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;
        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