128. Binary Tree Maximum Path Sum

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int max;
   
    public int maxPathSum(TreeNode root) {
        max = Integer.MIN_VALUE;
        dfs(root);
        return max;
    }
   
    public int dfs(TreeNode root) {
        if (root==null) return 0;
        int l = dfs(root.left);
        int r = dfs(root.right);
        int sum = root.val;
       
        if (l>0) sum+=l;
        if (r>0) sum+=r;
       
        max = Math.max(max, sum);
       
        return Math.max(l, r)>0? Math.max(l, r)+root.val: root.val;
    }
}