Binary Tree Maximum Path Sum

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int maxPathSum(TreeNode root) {
12         ArrayList<Integer> maxSum = new ArrayList<Integer>(1);
13         maxSum.add(Integer.MIN_VALUE);
14         getMaxSum(root,maxSum);
15         return maxSum.get(0);
16     }
17 
18     public int getMaxSum(TreeNode root,ArrayList<Integer> maxSum){
19         if(root==null){
20             return 0;
21         }
22     
23         int leftSum=0,rightSum=0;
24         leftSum = getMaxSum(root.left,maxSum);
25         rightSum = getMaxSum(root.right,maxSum);
26     
27         int curSum = Math.max(root.val,Math.max(root.val+leftSum,root.val+rightSum));
28         maxSum.add(0,Math.max(maxSum.get(0), Math.max(curSum,root.val+leftSum+rightSum)));
29         return curSum;
30     }
31 }