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

难度困难

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

分析

思路

• 路径每到一个节点，有 3 个选择：1. 停下不走。2. 走到左子节点。3. 走到右子节点。
• 走到子节点，又会面临三个选择。
• 不能走进一个分支，又掉头走另一个分支，不符合要求。

怎么选择，取决于“收益”

• 我们关心：如果走入一个子树，能从中获得最大收益是多少，不关心具体怎么走。
• 定义递归函数：计算当前子树能向父节点“提供”多大的「最大路径和」。
• 对于一条从父节点延伸下来的路径，它能在当前子树中获取的最大收益，分3种情况：
  1. 停在当前子树的根节点，最大收益：root.val。
  2. 路径走入左子树，最大收益：root.val + dfs(root.left)。
  3. 路径走入右子树，最大收益：root.val + dfs(root.right)。
• 递归的出口：遍历到 null 节点，返回 0，对外能提供的收益为 0。

负数情况的处理：

• 如果一个子树提供的「最大路径和」都为负，路径走入它，收益不增反减，我们希望这个子树完全被忽略，让它像 null 节点一样返回 0。

子树中的内部路径要包括根节点

• 题目说，路径不一定经过根节点，说明最大路径和可能产生于局部子树中。
• 每次递归求当前子树能向父节点提供多大的「最大路径和」时，都求一下「当前子树的最大路径和」，与全局的最大比较，试图刷新纪录。
• 一个子树内部的路径要贯穿根节点。为什么？
• 因为如果不贯穿根节点，则这条路径就不是当前子树的内部路径，是当前子树的子树的内部路径。
• 一个子树内部的最大路径和 = 左子树提供的最大路径和 + 根节点值 + 右子树提供的最大路径和。

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        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);
    }
}