leetcode124

 1 class Solution {
 2     int maxValue;
 3     public int maxPathSum(TreeNode root) {
 4         maxValue = Integer.MIN_VALUE;
 5         maxPathDown(root);
 6         return maxValue;
 7     }
 8     
 9     private int maxPathDown(TreeNode node) {
10         if (node == null) return 0;
11         int left = Math.max(0, maxPathDown(node.left));
12         int right = Math.max(0, maxPathDown(node.right));
13         maxValue = Math.max(maxValue, left + right + node.val);
14         return Math.max(left, right) + node.val;
15     }
16 }