leetcode_question_124 Binary Tree Maximum Path Sum

 
/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    int maxpathsum(TreeNode* root, int &depthsum)  
    {  
        if(root == NULL)return 0;  
        if(root->left == NULL && root->right == NULL)  
        {depthsum = root->val; return root->val;}  
  
        int maxsum = 0xC0000000;  
        int left = 0, lefthalf = 0;  
        if(root->left)  
            left = maxpathsum(root->left, lefthalf);  
        else  
        {left = 0xC0000000; lefthalf = 0xC0000000;}  
  
        int right = 0, righthalf = 0;  
        if(root->right)  
            right = maxpathsum(root->right, righthalf);  
        else  
        {right = 0xC0000000; righthalf = 0xC0000000;}  
  
        maxsum = lefthalf + root->val + righthalf;  
        maxsum = left > maxsum ? left : maxsum;  
        maxsum = right > maxsum ? right : maxsum;  
        lefthalf = lefthalf > righthalf ? lefthalf : righthalf;  
        depthsum = lefthalf + root->val > root->val ? lefthalf+root->val : root->val;  
        maxsum = maxsum > depthsum ? maxsum : depthsum;  
        maxsum = maxsum > root->val ? maxsum : root->val;  
        return maxsum;  
    }  
    int maxPathSum(TreeNode *root) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        if(root == NULL)return 0;  
        int maxsum = 0;  
        int depthsum = 0;  
        maxsum = maxpathsum(root, depthsum);  
        maxsum = depthsum > maxsum ? depthsum : maxsum;  
        return maxsum;  
    }  
};