Binary Tree Maximum Path Sum leetcode

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

这道题包涵root在内的最大值有四种情况：
 1.root本身（可能有负数存在的情况）
 2. root+左子树
 3.root+ 右子树
 4.root + 左子树 + 右子树 解题
因为需要一个位置来存储最大值， 所以新建一个helper函数 把最大值存入一个数组里， 这样便利完整个树之后最大值久得到了。
这里注意result的初始值应该是Integer.MIN_VALUE

解题思路就是找到最大的一条更新到result[0]里面 （java无法按引用传，就只能建立一个数组）
1,2,3 三部需要用来当前root分支的最大值（4情况不算是root的分支了）， 所以要传回去

算法的本质还是一次树的遍历，所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。

public class Solution {
    public int maxPathSum(TreeNode root) {
        int[] result = new int[1];
        result[0] = Integer.MIN_VALUE;
        helper(result, root);
        return result[0];
    }
    public int helper(int[] result, TreeNode root){
        if (root == null){
            return 0;
        }
        //divide
        int left = helper(result, root.left);
        int right = helper(result, root.right);
        //Conquer
        int max = Math.max(root.val, Math.max(root.val + left, root.val + right));//找1,2,3的最大值返回
        result[0] = Math.max(result[0], Math.max(max, root.val + left + right));//把4步里的最大值和result[0]比较，返回最大的为result[0]
        return max;
    }
}