Binary Tree Maximum PathSum

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.

Solution: this answer use a post-order traversal. Note that in Java we cannot pass int variables by reference, therefore we need to pass an ArrayList object to keep and modify the current max value.

Java语言: BinaryTreeMaxPathSum

01 public int maxPathSum(TreeNode root) {
02     ArrayList<Integer> temp = new ArrayList<Integer>(1);
03     temp.add(Integer.MIN_VALUE);
04     maxSubPath(root, temp);
05     return temp.get(0);
06 }
07 
08 public int maxSubPath(TreeNode root, ArrayList<Integer> temp) {
09     if (root == null)  return 0;
10     int leftMax = Math.max(0, maxSubPath(root.left, temp));
11     int rightMax = Math.max(0, maxSubPath(root.right, temp));
12     int curr_max=temp.get(0);
13     int new_max= root.val+leftMax+rightMax;
14       //update the max path sum
15     if(new_max>curr_max)
16         temp.set(0, new_max);
17     //calculate the max sub path, 
18     //either on left branch or right branch
19     return Math.max(root.val+leftMax, root.val+rightMax);
20 }