Soution in C passing special judge


  • 1
    S

    The commom solution gives TLE
    Special Judge: very large tree

    Special Judge: very large tree
    int countNodes(struct TreeNode* root) {

    if(root==NULL)
        return 0;
    
    return 1+ countNodes(root->left)+countNodes(root->right);
    

    }

    Now , Take the benefit of case when tree is full tree i.e. (2^h -1) is the solution

    if it is not full tree then follow above solution

    int countNodes(struct TreeNode* root) {

    if(root==NULL)
        return 0;
        
     int height_l=0,height_r=0;
    struct TreeNode *p=root;
    while(NULL!=p){
        ++height_l;
        p=p->left;
    }   
    p=root;
    
    while(NULL!=p){
        ++height_r;
        p=p->right;
    }  
    
    if(height_r==height_l){
        return (1<< height_l)-1;   //pow(2,height_l)-1;//2^h-1
    }
    
    return 1+ countNodes(root->left)+countNodes(root->right);
    

    }


Log in to reply
 

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