Max Sum Path in Binary Tree

Given a binary tree T, find the maximum path sum.

The path may start and end at any node in the tree.

The first and the only argument contains a pointer to the root of T, A.

Return an integer representing the maximum sum path.

1 <= Number of Nodes <= 7e4
-1000 <= Value of Node in T <= 1000

Input 1:

       1
      / \
     2   3

Output 1:
     6

Explanation 1:
    The path with maximum sum is: 2 -> 1 -> 3

Input 2:
    
       -10
       /  \
     -20  -30

Output 2:
    -10

Explanation 2
    The path with maximum sum is: -10

Solution:

Time: O(n)
Space: O(n)

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {
 *      val = x;
 *      left=null;
 *      right=null;
 *     }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode A) {
        // at each level, calculate the max
        // and return max path containing current root
        int[] max = new int[1];
        max[0] = Integer.MIN_VALUE;
        dfs(A, max);
        return max[0];
    }
    
    private int dfs(TreeNode A, int[] max) {
        if (A == null) return 0;
        int left = dfs(A.left, max);
        int right = dfs(A.right, max);
        int leftSum = A.val + left;
        int rightSum = A.val + right;
        max[0] = Math.max(max[0], Math.max(A.val, Math.max(leftSum, rightSum)));
        max[0] = Math.max(max[0], left + right + A.val); 
        return Math.max(A.val, Math.max(leftSum, rightSum));
    }
}