dfs深度优先搜索，对于每一个节点，有两种角色：
1、作为根节点，计算构建的树的最大路径和，此时需要left+right+rootVal,因为可以只取一部分，所以要判断左右的值是否小于0，负数的话就是舍弃。但是root本身是不是负数不需要关心，因为对于一棵树而言，最大路径和无非就是root，left，right，root+left，root+right，root+left+right,left和right在下一次自己作为根节点的时候会去和res比较取最大值的，而rootVal+left+right>=rootVal,不管rootVal是什么值，都保留了较大的那个值。
2、作为子树，返回的时候根据题目意思，就只能取rootVal+Math.max(left,right);
import java.util.*;

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

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int res=Integer.MIN_VALUE; 
    public int maxPathSum (TreeNode root) {
        dfs(root);
        return res;
    }
    int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        //作为根树计算的时候
        int rootVal=root.val;
        int left=Math.max(dfs(root.left),0);
        int right=Math.max(dfs(root.right),0);
        res=Math.max(res,rootVal+left+right);
        return rootVal+Math.max(left,right);  //作为子树返回的时候
        
        
    }
}