[LeetCode] 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.

 解题思路：
 1. 对于任何一个node, 有四种path情况需要考虑：
  1.1 仅有node
  1.2 左子树+node
  1.3 node + 右子树
  1.4 左子树 + node + 右子树

为了求最大的path sum. 我们需要从1-3中选出最大的返回给parent，从1-4中选出最大的作为备选的最后结果path sum.

Java Code:

public int maxPathSum(TreeNode root){
       int[] max = new int[1];
       max[0] = Integer.MIN_VALUE;
       maxSum(root, max);
       
       return max[0];
    }
    
    public int maxSum(TreeNode root, int[] max){
        int val = 0, left = 0, right = 0;
        
        val = root != null ? root.val : 0;   
        left = root.left != null? maxSum(root.left, max) : 0;
        right = root.right != null ? maxSum(root.right, max) : 0;
        
        int currMax = val;
        
        if(left > 0) currMax += left;
        if(right > 0) currMax += right;
        max[0] = max[0] > currMax? max[0] : currMax;
        
        if(left > 0 && left >= right) return val + left;
        if(right > 0 && right > left) return val + right;
        
        return val;
    }