题解 | #二叉树中的最大路径和#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    static int maxSum = Integer.MIN_VALUE;;
    
    public int maxPathSum (TreeNode root) {
        gainMax(root);
        return maxSum;
    }
    
    //包括头节点时，经过头节点至叶子节点的累加和的最大值
    public static int gainMax(TreeNode root){
        if (root == null){
            return 0;
        }

        //左节点所能提供的最大累加和,只有大于0，才会被选择
        int leftGainMax = Math.max(0, gainMax(root.left));
        //右节点所能提供的最大累加和
        int rightGainMax = Math.max(0, gainMax(root.right));
        //经过该头节点所能达到的最大值
        int rootGainMax = root.val + leftGainMax + rightGainMax;
        //更新最大值数据
        maxSum = Math.max(maxSum, rootGainMax);
        //返回值只包括左右中较大的一部分
        return root.val + Math.max(leftGainMax, rightGainMax);
    }
}