Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1: Input: [1,2,3]

       1
      / \
     2   3

Output: 6 Example 2: Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

class Solution {
    public int maxPathSum(TreeNode root) {
        int[] res = {Integer.MIN_VALUE};
        maxSingle(root, res);
        return res[0];
    }

    private int maxSingle(TreeNode root, int[] res) {
        if(root == null) return 0;

        int left = maxSingle(root.left, res); //左边一支，不算自己
        int right = maxSingle(root.right, res); //右边一支，不算自己

            //int single为一支的最大值，要么root自己（左右都小于等于0），要么root自己加上左右中较大的一支。
            //这个int single是为了return，此maxSingle方法完整的作用是找到单条sum最大，我们利用这个方法去存储整条最大的值
        int single = Math.max(root.val, Math.max(left, right) + root.val); 
        int arc = left + right + root.val; //左中右都加起来的值
        int max = Math.max(arc, single); 
        if(max > res[0]) res[0] = max; //更新max
        return single;
    }
}