Binary Tree Maximum Path Sum (LeetCode Tree)

Question: 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.

Idea: This problem seems quite hard since Java can not return multiple values in a function. However, by adding a class member variable, we can solve the problem as easy as in Python.

The path sum is consisted of three components: the maximum subroutine in the left subtree, the root.val, and the maximum subroutine in the right subtree.  Let us have a look two examples:

            1                                            1
       2           3                              2          1
    4   1                                       4   5
      (Example 1)                           (Example 2)

For the node 2 in example 1, it will better to contribute itself as a subroutine to form 4-2-1-3 the maximum. However, in example 2, the maximum path sum 4-2-5 is inside the subtree rooted at 2. So for any node x, there are two possible choices: 1) the maximum path sum is inside a subtree rooted at x, or  2) the subtree rooted at x will contribute a subroutine to x's parent. However, we do not know which choice is better. So we need to compare all of the choices to get the maximum.

The algorithm runs like this:
1) For each node x, calculate the maximum path sum inside the subtree rooted at x.
2) Update the result=max(result, this subtree's maximum)
3) return x's longest subroutine to x's parent for next comparison.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   int maxValue;  
   public int maxPathSum(TreeNode root) {  
     if(root==null)  
       return 0;  
     maxValue=Integer.MIN_VALUE;  
     maxPathDown(root);  
     return maxValue;  
   }  
   public int maxPathDown(TreeNode root)  
   {  
     if(root==null)  
       return 0;  
     int left=Math.max(maxPathDown(root.left),0);  
     int right=Math.max(maxPathDown(root.right),0);  
     maxValue=Math.max(maxValue,left+right+root.val);  
     return Math.max(left,right)+root.val;  
   }  
 }