Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:

Given the below binary tree,

1      / \     2   3

 

Return 6.

 

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 int max = Integer.MIN_VALUE;12     public int maxPathSum(TreeNode root) {13         if (root == null) {14             return 0;15         }16         maxSum(root);17         return max;18     }19 20     private int  maxSum(TreeNode root) {21         if (root == null) {22             return 0;23         }24         int leftSum=0;25         int rightSum=0;26         int val=root.val;27         if (root.left != null) {28             leftSum = maxSum(root.left);29             if (leftSum > 0) {30                 val = val + leftSum;31             }32         }33 34         if (root.right != null) {35             rightSum = maxSum(root.right);36             if (rightSum > 0) {37                 val = val + rightSum;38             }39         }40 41         if (val > max) {42             max = val;43         }44 45         return Math.max(root.val, Math.max(root.val + leftSum, root.val + rightSum));46 47 48     }49 }