[LeetCode] Binary Tree Maximum Path Sum

Problem:

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:O(n)

public class Solution {
    public int maxPathSum(TreeNode root) {
        int[] ret = maxPathSums(root);
        return ret[1];
    }
    
    public int[] maxPathSums(TreeNode root){
        int[] ret = new int[2];
        if(root==null){
            ret[0]=Integer.MIN_VALUE;
            ret[1]=Integer.MIN_VALUE;
            return ret;
        }
        int[] maxLeft = maxPathSums(root.left);
        int[] maxRight = maxPathSums(root.right);
        
        int tmp1 = maxLeft[0]>0?(maxLeft[0]+root.val):root.val;
        int tmp2 = maxRight[0]>0?(maxRight[0]+root.val):root.val;
        
        ret[0]=Math.max(tmp1,tmp2);
        ret[1]=Math.max(maxLeft[1],Math.max(maxRight[1], Math.max(tmp1+tmp2-root.val,ret[0])));
        
        return ret;
    }
}

Key Concept: Hold max path from left to right and to root at each node