Leetcoder - Binary Tree Maximum Path Sum

 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.

/**
 * 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 max = root.val;
     
        return getSum(root, max)[0];
    }
 
    public int[] getSum(TreeNode node, int max) {
        int[] vals = new int[2];
        vals[0] = max;
        vals[1] = node.val;
        int leftSum = 0;
        int rightSum = 0;
        int sum = node.val;
        if(node.left!=null) {
            int[] leftV = getSum(node.left, max);
            leftSum = leftV[1] + node.val;
            if(leftV[0]>max) {
                max = leftV[0];
            }
            if(leftV[1]>0) {
                sum += leftV[1];
            }
        }
        if(node.right!=null) {
            int[] rightV = getSum(node.right, max);
            rightSum = rightV[1] + node.val;
            if(rightV[0]>max) {
                max = rightV[0];
            }
            if(rightV[1]>0) {
                sum += rightV[1];
            }
        }
        if(leftSum>vals[1]) {
            vals[1] = leftSum;
        }
        if(rightSum>vals[1]) {
            vals[1] = rightSum;
        }
        if(sum>max) {
            vals[0] = sum;
        } else {
            vals[0] = max;
        }
        return vals;
    }
}


public class Solution {
   
    private int maxSum = 0;
   
    public int maxPathSum(TreeNode root) {
        if(root==null) return 0;
        maxSum = root.val;
        getPathSum(root);
        return maxSum;
    }
   
    private int[] getPathSum(TreeNode root) {
        int[] sums = new int[2];           
        sums[0] = root.val;
        sums[1] = root.val;
        if(root.left==null && root.right==null) {
            maxSum = Math.max(maxSum, root.val);
            return sums;
        }
        if(root.left!=null) {
            int[] leftSum = getPathSum(root.left);
            sums[0] = Math.max(0, Math.max(leftSum[0], leftSum[1])) + root.val;
        }
        if(root.right!=null) {
            int[] rightSum = getPathSum(root.right);
            sums[1] = Math.max(0, Math.max(rightSum[0], rightSum[1])) + root.val;
        }
        maxSum = Math.max(maxSum, Math.max(sums[0]+sums[1]-root.val, Math.max(sums[0], sums[1])));
        return sums;
    }
}


===========

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   
    int max = Integer.MIN_VALUE;
   
    public int maxPathSum(TreeNode root) {
        max = Integer.MIN_VALUE;
        helper(root);
        return max;
    }
   
    private int helper(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(0, helper(node.left));
        int right = Math.max(0, helper(node.right));
       
        max = Math.max(max, left + right + node.val);
       
        return node.val + Math.max(left, right);
    }
}