Binary Tree Maximum Path Sum

题目地址：
https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

题目：

Given a 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.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

解题思路：
这道题主要就是用dfs，从左边要一个值，从右边要一个值，然后先更新max，然后再返回某一支。

代码：

private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    if(root == null){
        return max;
    }
    helper(root);
    return max;
}

private int helper(TreeNode root){
    if(root == null){
        return Integer.MIN_VALUE;
    }
    int left = Math.max(helper(root.left), 0);
    int right = Math.max(helper(root.right), 0);
    max = Math.max(max, root.val + left + right);
    return root.val + Math.max(left, right);
}