对于树的题目练习的太少，一般就是dfs，这里也是如此，采用递归来实现。不过我们递归的返回值不是我们所需要的值，我们所需要的值是需要在递归函数里面进行更新，这一步很重要，要能分清楚。 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int max=Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        // write code here
        maxPath(root);
        return max;
    }
     public int maxPath (TreeNode root) {
         if(root==null) return 0;
          // 只有在最大贡献值大于 0 时，才会选取对应子节点
         int maxLeft=Math.max(0,maxPath(root.left));
         int maxRight=Math.max(0,maxPath(root.right));
         //max是要返回的值，所以要把maxLeft和maxRight以及root.val加起来然后更新
         max=Math.max(max,root.val+maxRight+maxLeft);
         //返回节点的最大贡献值 该节点要和其他节点连起来 返回的是Math.max(maxRight,maxLeft)+root.val而不是root.val+maxRight+maxLeft
         //这里不能和上面对max更新弄混
         return Math.max(maxRight,maxLeft)+root.val;
     }
}
maxPath的最后两行代码要着重理解，理解递归函数的返回值不是我们需要返回的结果，返回的结果是需要在递归函数中更新出来进行返回，递归只是我们更新结果的步骤。