二叉树中的最大路径和

/*
 * 思路：
 * 我们需要找到二叉树中的最大路径和。路径可以从任何节点开始，到任何节点结束，且每个节点至多出现在路径中一次。
 * 使用递归的方法来解决这个问题。我们定义一个辅助函数 maxGain(node)，它计算从节点 node 出发的最大贡献值。
 * 对于每个节点，考虑两种情况：
 * 1. 当前节点独立成一个路径的起点，那么最大路径和是 node.val + maxGain(node.left) + maxGain(node.right)
 * 2. 当前节点作为上一级路径的一部分，那么最大贡献值是 node.val + max(maxGain(node.left), maxGain(node.right))
 * 
 * 在递归过程中，我们会不断更新全局的最大路径和。
 * 
 * 这里使用Java Stream API来简化代码
 */

import java.util.stream.Stream;

class Solution {
    private int maxSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    
    private int maxGain(TreeNode node) {
        if (node == null) return 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 + Stream.of(leftGain, rightGain).mapToInt(Integer::intValue).max().orElse(0);
    }
}