编程之美 两个叶子的节点之间 最大距离 变种 leecode

提交地址：

https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/

说一下思路http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html这是编程之美那个题目的另一种解法思路更简单,那个题目求路径节点数，而这个是路径和，这是最简单的一种思路

对于每一个节点：

maxSum :一个属性，最后的值就是它，是他，是他，小哪吒；

max(root)函数返回的是，包含root的到其子树的最大和

max(root)= 最大（ max(root.left)+root.val,max(root.right)+root.val,root.val)

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxSum=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root==null) return 0;
        
           max(root);
           return maxSum;
        
        
        
}
     public int max(TreeNode root) 
     {  if(root==null) return 0;
     
        int left=max(root.left);
        int right=max(root.right);
        
        int maxtemp=root.val;
        
        if(left>0) maxtemp+=left;
        if(right>0) maxtemp+=right;
        if(maxtemp>maxSum) maxSum=maxtemp;
        
        
        return Math.max(0,Math.max(left,right))+root.val;
        
     
     
           
          
         
         
     }
}