124 Binary Tree Maximum Path Sum ****Attention

很有意思

Given anon-emptybinary 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 containat least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

题意理解的就完全不对！！或者说不够

意思是 从一个节点出发的一条路径，

比如从15- 》 9 -〉 3 -》 20

15 - 〉 9 -》 7但是不能到3，因为7和3不连着

          3
         / \
        9  20
      /  \
     15   7



          3              
         / \
        9  20
       /        
     15               

        9  
      /  \
     15   7

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        helper(root); // postorder traversal of the binary tree
        return max;
    }
    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // postorder
        int sum = 0;
        int left = Math.max(0, helper(root.left));
        int right = Math.max(0, helper(root.right)); 
        max = Math.max(max, left + right + root.val);
        sum = Math.max(left, right) + root.val;
        //by choosing the maximum from left child and right child, we choose one larger value path
        //this is important, the return value for each node is different from 
        //the way we calculate the sum, when calculating the maxmum sum of the path, we add up the left.val and right.val
        // and the root.val
        return sum;
    }
}