Someone help, why this code is not working?


  • 0
    D
     int maxPathUtil(TreeNode * root,int *max,int *cur)
    {
        if(!root)
            return 0;
        else if(!root->left && !root->right)
        {
            *cur+=root->val;
            if(*cur>*max)
                *max= *cur;
        }
        else
        {
            *cur += root->val;
            maxPathUtil(root->left,max,cur);
            maxPathUtil(root->right,max,cur);
        }
    }
    int maxPathSum(TreeNode* root) {
        
        int *max=0,*cur=0;
        if(!root)
            return 0;
         maxPathUtil(root,max,cur);
         return *max;
        
    }

  • 0
    D

    The way that you use pointers is wrong.

    int *max=0,*cur=0;
    maxPathUtil(root, max, cur);
    

    This means max and cur are NULL pointers. Then when you access them inside maxPathUtil(), you will get run time error.
    The parameter cur is not needed. Your code only update max for leaf node, but the path can start and end at ANY node in the tree.

    Below code passed the tests.

    int maxPathUtil(struct TreeNode *root, int *max)
    {
        if (!root)
            return 0;
        int left  = maxPathUtil(root->left, max);
        int right = maxPathUtil(root->right, max);
        int total = left + right + root->val;
        if (total > *max)
            *max = total;
        int max_path = root->val + (left > right ? left : right);
        return max_path > 0 ? max_path : 0;
    }
    
    int maxPathSum(struct TreeNode* root) {
    
        int max = -0x80000000;
        maxPathUtil(root, &max);
        return max;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.