124. Binary Tree Maximum Path Sum

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

Return6.

思路：受到股票启发

public class Solution {
    int maxVal = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {    
        helper(root);
        return maxVal;
    }

    // helper returns the max branch 
    // plus current node's value
    public int helper(TreeNode root){
        if (root==null) return 0;
        int left = Math.max(helper(root.left),0);
        int right = Math.max(helper(root.right),0); 

        maxVal = Math.max(maxVal,root.val+left+right);

        return root.val+Math.max(left,right);
    }
}