【leetcode hot 100 124】二叉树中的最大路径和

解法一：（递归）考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体而言，该函数的计算如下。

• 空节点的最大贡献值等于 0。
• 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxSum = Integer.MIN_VALUE; // 全局变量记录最大值

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

    public int maxRoot(TreeNode root){
        // 计算root节点的最大贡献值
        if(root==null){
            return 0;
        }

        // 左右节点我们只取大于0的节点(不取负数，以得到maxSum的最大值)
        int left = Math.max(maxRoot(root.left),0);
        int right = Math.max(maxRoot(root.right),0);

        // 更新全局最大值
        int newPath = root.val + right + left;
        maxSum = Math.max(maxSum, newPath);
		
		// 返回值
        return root.val + Math.max(right,left);
    }
}

注意：

• 递归函数maxRoot的作用为计算root节点的最大贡献值
• 全局变量maxSum的作用为记录最大路径和
• 递归左右节点时，我们只取大于0的节点(不取负数，以得到maxSum的最大值)：int left = Math.max(maxRoot(root.left),0);
• 更新最大值时，要考虑当前节点值+左节点最大贡献值+右节点最大贡献值，然后和maxSum取最大值
• 返回值为：root.val + Math.max(right,left)