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.

Example

Given the below binary tree,

       1
      / \
     2   3

 
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
     int helper(TreeNode *root, int &maxSum) {
        if (!root)  return 0;
            
        int lPath = helper(root->left, maxSum);
        int rPath = helper(root->right, maxSum);
        
        int sum = root->val + lPath+ rPath;
        maxSum = max(maxSum, sum);
        
        return max(0, root->val + max(lPath,rPath));
    }
    
    int maxPathSum(TreeNode *root) {
         int maxPath = INT_MIN;
         helper(root, maxPath);
         return maxPath;
    }
};