题目：

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 4

/ \

2 3

The highlighted path yields the maximum sum 10

 

解答：

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 }