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.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
  #define INT_MIN 0x8FFFFFFF


  int MPSRecurse(TreeNode *root, int *sum)  
   {  
     if(root == NULL)return INT_MIN;  
     if(root->left == NULL && root->right == NULL)  
     {  
       *sum = root->val;  
       return root->val;  
     }  
     int lsum = INT_MIN, rsum = INT_MIN;  
     int x = MPSRecurse(root->left, &lsum);  
     int y = MPSRecurse(root->right, &rsum);  
     *sum = max(max(lsum,rsum)+root->val,root->val);  
     if(lsum<0)lsum = 0;  
     if(rsum<0)rsum = 0;  
     return (max(max(x,y), lsum + rsum + root->val));  
   }


  
   int maxPathSum(TreeNode *root) {  
     int sum = 0;  
     return MPSRecurse(root, &sum);  
   }