124. Binary Tree Maximum Path Sum

比较有意思的题，不过算不上hard tag.
这里我们记录一个max(用int[]是为了不使用global)来记录max path sum(可以是任意node为起点终点，整条path大于等于一个node就可以。也要注意这里的node值可以是负数。

helper函数的定义是以root为最高根所能找到的max sum path的sum值，我么分别求出以root的左孩子和右孩子为最高点所能找到的max sum path的sum.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 
 
        1
      /   \
     2     3
    / \   / \
   5   3 9   4
 
max[0]: maxPathSum  
helper method 1.returns path sum that can be extended to the parent of input root 5-2 can, 5-2-3 can not 
              2.computes max path sum with higest node the input root (left + right + root.val) and update the max path sum   
use max(0, helper(root.left, max))  to calculate left and right to avoid change codes when l,r < 0
 */
class Solution {
    public int maxPathSum(TreeNode root) {
        if (root == null){
            return 0;
        }
        int[] max = new int[1];
        max[0] = Integer.MIN_VALUE;
        helper(root, max);
        return max[0];   
    }
    
    private int helper(TreeNode root, int[] max){
        if (root == null){
            return 0;
        }
        int left = Math.max(0,helper(root.left, max));
        int right = Math.max(0,helper(root.right, max));
        max[0] = Math.max(max[0],left + right + root.val);
        return Math.max(left, right) + root.val;
    }
}