What's wrong with my C code?


  • 0
    D
    struct pathrecorder
    {
        int val;
        int maxpathvalue;
        struct pathrecorder *left;
        struct pathrecorder *right;
    };
    struct pathrecorder* buildNewTree(struct TreeNode* root)
    {
        struct pathrecorder *result=malloc(sizeof (struct pathrecorder));
        result->val=root->val;
        if(root->left==NULL && root->right==NULL)
        {
            result->left=NULL;
            result->right=NULL;
            result->maxpathvalue=root->val;
        }
        if(root->left!=NULL && root->right==NULL)
        {
            result->left=buildNewTree(root->left);
            if(result->left->maxpathvalue>0)
                result->maxpathvalue=result->val+((result->left)->maxpathvalue);
            else
                result->maxpathvalue=result->val;
        }
        
        if(root->left==NULL && root->right!=NULL)
        {
            result->right=buildNewTree(root->right);
            if(result->right->maxpathvalue>0)
                result->maxpathvalue=result->val+((result->right)->maxpathvalue);
        
            else
                result->maxpathvalue=result->val;
        } 
        if(root->left!=NULL && root->right!=NULL)
        {
            result->right=buildNewTree(root->right);
            result->left=buildNewTree(root->left);
            if(((result->right)->maxpathvalue)>((result->left)->maxpathvalue))
            {
            
                result->maxpathvalue=((result->right)->maxpathvalue)+result->val;
            }
            else if (((result->right)->maxpathvalue)<((result->left)->maxpathvalue))
            {
              
                result->maxpathvalue=((result->left)->maxpathvalue)+result->val;
            }
            else if (((result->right)->maxpathvalue)==((result->left)->maxpathvalue))
            {
        
                result->maxpathvalue=((result->left)->maxpathvalue)+result->val;
            }
            
            if (((result->right)->maxpathvalue)<0 && 0>((result->left)->maxpathvalue))
            {
      
                result->maxpathvalue=result->val;
            }
        }
        
        
        
        return result;
    }
    int max;
    
    void traverse(struct pathrecorder* root)
    {
        
        int r;
        if((root->left)!= NULL && (root->right)!=NULL)
        {    
            r=((root->left)->maxpathvalue)+(root->val)+((root->right)->maxpathvalue);
            
            if(r>max)
                max=r;
            if((root->maxpathvalue)>max)
                max=root->maxpathvalue;
            
            traverse(root->left);
            traverse(root->right);
        
        }
        if(root->left==NULL && root->right==NULL)
            if(root->val>max)
                max=root->val;
        if(root->right==NULL && root->left!=NULL)
        {
            if(root->maxpathvalue>max)
                max=root->maxpathvalue;
            traverse(root->left);
            
        }
        if(root->left==NULL && root->right!=NULL)
        {
            if(root->maxpathvalue>max)
                max=root->maxpathvalue;
            traverse(root->right);
            
        }
        
        
    }
    
    int maxPathSum(struct TreeNode* root)
    {
        
        struct pathrecorder *newroot=malloc(sizeof(struct pathrecorder));
        newroot=buildNewTree(root);
        max=newroot->maxpathvalue;
        traverse(newroot);
       
        return max;
    }
    

    Here is my code. My idea is pretty straightforward. I use "buildNewTree" to build a new tree with a "maxpathvalue", which is used to record the max path GOING DOWN. Then I use my "traverse" to scan the new tree, campare "r=((root->left)->maxpathvalue)+(root->val)+((root->right)->maxpathvalue)" and "max" then get the result. What kills me is that the program works WELL with small scale tree, but it will go runtime error with large scale tree. I really appreciate any help or suggestion.


  • 0
    C

    Are you trying to solve this problem by starting from every node and then reaching out? This should give you O(N^2) time complexity.

    We can solve this problem with O(N) time complexity by a bottom-to-up solution.


Log in to reply
 

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