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:
We cannot traverse from a child node to its parent node, so we need to use recursion to send "feedback" to a parent node. 
For each node, we calculate its max path sum. Since a path sum could be negative, so we will compare all candidates: root, root+left, root+right, root+left+right, and  the "feedback" would be max of root, root+left, and root+right. 

// a node may have a positive val.
public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root == null)
            return 0;
        helper(root);
        return max;
    }
    // return max single path sum
    public int helper(TreeNode root){
        if(root == null)
            return 0;
            
        int maxLeft = helper(root.left);
        int maxRight = helper(root.right);
        
        int maxSinglePath = Math.max(maxLeft + root.val, maxRight + root.val);
        maxSinglePath = Math.max(maxSinglePath, root.val);
        
        max = Math.max(max, root.val);
        max = Math.max(max, maxSinglePath);
        max = Math.max(max, maxLeft + maxRight + root.val);
        
        return maxSinglePath;
    }
}