Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example: Given the below binary tree,
Return 6.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { int maxValue = Integer.MIN_VALUE; public int maxPathSum (TreeNode root) { maxSum(root); return maxValue; } public int maxSum (TreeNode root) { if (root == null ) return 0 ; int leftSum = Math.max(0 , maxSum(root.left)); int rightSum = Math.max(0 , maxSum(root.right)); maxValue = Math.max(maxValue, root.val + leftSum + rightSum); return root.val + Math.max(leftSum, rightSum); } }