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.

Solution:
recursive function, returns the maximum single sided sum, and updates the maximum double sided sum while doing the recursion.


public class Solution {
    int findMaxSingleSide(TreeNode root, int[] max){
        if(root == null) {
            return 0;
        }
        int left = findMaxSingleSide(root.left,max);
        int right = findMaxSingleSide(root.right,max);
        int longer = Math.max(left,right);
        int result = Math.max(root.val, root.val+longer);
       
        int newMax = root.val;
        newMax = Math.max(newMax, newMax + left);
        newMax = Math.max(newMax, newMax + right);
        max[0] = Math.max(max[0], newMax);
       
        return result;
    }
    public int maxPathSum(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root == null) return 0;
        int[] ret = new int[1];
        ret[0] = root.val;
       
        findMaxSingleSide(root, ret);
        return ret[0];
    }
}