Binary Tree Maximum Path Sum

 1 public class Solution {
 2     private int maxSum;
 3 
 4     public int getPathSum(TreeNode root) {
 5         maxSum = Integer.MIN_VALUE;
 6         findMax(root);
 7         return maxSum;
 8     }
 9 
10     private int findMax(TreeNode p) {
11         if(p == null) {
12             return 0;
13         }
14 
15         int left = findMax(p.left);
16         int right = findMax(p.right);
17 
18         maxSum = Math.max(p.val + left + right, maxSum);
19         int ret = p.val + Math.max(left, right);
20         return ret > 0? ret:0;
21     }
22 
23 
24 }