Leetcode Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum Nov 8 '12
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.

Leetcode Binary Tree Maximum Path Sum.java

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[] result = recersiveMax(root);
        return Math.max(result[0], result[1]);
        
    }
    
    public int[] recersiveMax(TreeNode root){
        int[] result = new int[2];
        
        if(root.right == null && root.left == null){
            result[0] = root.val;
            result[1] = root.val;
        }
        else if(root.right == null || root.left == null){
            TreeNode noNull = (root.left == null)? root.right: root.left;
            int[] nos = recersiveMax(noNull);
            result[0] = Math.max(root.val, nos[0] + root.val);
            result[1] = Math.max(nos[1], nos[0] + root.val);
            result[1] = Math.max(result[1], root.val);
        }
        else{
            int[] left = recersiveMax(root.left);
            int[] right = recersiveMax(root.right);
        
            result[0] = Math.max(left[0] + root.val, right[0] + root.val);
            result[0] = Math.max(result[0], root.val);
        
            result[1] = Math.max(left[1], right[1]);
            result[1] = Math.max(result[1], left[0] + right[0] + root.val);
            result[1] = Math.max(result[1], root.val);
        }
        
        return result;
        
        
    }
}