124. Binary Tree Maximum Path Sum

需要注意localMax无论如何必须包含root.val
即使root.val是负值
19.36 % 
public class Solution {
    private Integer globalMax;
    public int maxPathSum(TreeNode root) {
        globalMax = Integer.MIN_VALUE;
        maxPathSumHelper(root);
        return globalMax;
    }
 
    /*
    global max
    leftSum, rightSum
    */
    private int maxPathSumHelper(TreeNode root) {
        if (root == null) return 0;
        int leftSum = maxPathSumHelper(root.left);
        int rightSum = maxPathSumHelper(root.right);
        int localMax = root.val;
        localMax += leftSum < 0 ? 0 : leftSum;
        localMax += rightSum < 0 ? 0 : rightSum;
     
        globalMax = Math.max(globalMax, localMax);
        return root.val + Math.max(0, Math.max(leftSum, rightSum));
    }
 
}