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 * 10^4]
• -1000 <= Node.val <= 1000

这道题和543二叉树的直径很像，都是从任意节点到任意节点，都不一定经过根节点。路径都不会分叉。

DFS-分治-后序

递归计算从当前节点出发的最大贡献值（取正值，贡献不能是拖后腿的），不能是经过当前节点的最大贡献值， 不然可能和根节点连不上。每次递归都保存最大值，因为有可能最大路径和并不经过输入的树的根节点，而是经过某个子树的根节点。

计算以每个节点为根节点（即经过当前节点）的最大路径和，取最大值即可。

如何计算最大路径和呢？只需计算以左右子节点为起点的最大路径和，相加再加当前节点的值即可。

所以我们的递归方法是计算以当前节点为起点的最大路径和，在后序部分计算经过当前节点的最大路径和即可。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // 初始化全局变量 maxSum，用以存储遍历过程中找到的最大路径和
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        // 调用递归函数开始计算，并返回结果
        maxGain(root);
        return maxSum;
    }

    // 递归函数计算从当前节点出发的最大贡献值（或者说不分叉的路径的和），并更新全局的最大路径和。注意，一定是从当前节点出发的，不然路径可能连不上。
    // 注意返回值是以当前节点为起点的最大路径和，这样才具有递归性。
    public int maxGain(TreeNode node) {
        // 递归的基准情况，如果当前节点为空，则此节点的最大贡献值为0
        if (node == null) {
            return 0;
        }
        
        // 递归地计算左子节点的最大贡献值，只有当贡献值大于0时才考虑该子节点贡献值。重点是取正。
        int leftGain = Math.max(maxGain(node.left), 0);
        // 同上，递归地计算右子节点的最大贡献值
        int rightGain = Math.max(maxGain(node.right), 0);

        // 当前节点的最大路径和为该节点的值加上左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;
        // 注意，更新全局最大路径和。最大路径和不具有递归性，所以需要每次计算。即根节点不一定是最大路径和的根节点。
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回当前节点的最大贡献值。注意这里是取最大值，不是把左右子树的结果相加。因为路径不能分叉。
        return node.val + Math.max(leftGain, rightGain);
    }
}

• 时间复杂度: $O(N)$，其中 $N$ 是二叉树中的节点个数。对每个节点访问不超过 2 次。
• 空间复杂度：$O(N)$，其中 $N$ 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。