From a naive traversal to two different simple clean recursive solutions and an optimized one in C


  • 0
    int leftHeight(struct TreeNode* root)
    {
        return !root? 0 : 1+leftHeight(root->left);
    }
    
    //AC - 152ms;
    int countNodes(struct TreeNode* root)
    {
        if(!root) return 0;
        int lHeight = leftHeight(root->left);
        int rHeight = leftHeight(root->right);
        return lHeight == rHeight? pow(2, lHeight)-1 : (1 << rHeight) + countNodes(root->left);
    }
    
    //AC - 144ms;
    int countNodes(struct TreeNode* root)
    {
        if(!root) return 0;
        int lHeight=0, rHeight=0;
        for(struct TreeNode* l=root; l; l=l->left) lHeight++;
        for(struct TreeNode* r=root; r; r=r->right) rHeight++;
        if(lHeight==rHeight) return (1<<lHeight)-1; 
        return countNodes(root->left)+countNodes(root->right)+1;
    }
    
    //AC - 90ms
    int countNodes(struct TreeNode* root)
    {
        if(!root) return 0;
        int lHeight=0;
        int rHeight=0;
        for(struct TreeNode* t=root->left; t; t=t->left) lHeight++;
        for(struct TreeNode* t=root->right; t; t=t->left) rHeight++;
        if(lHeight==rHeight) 
        {
            rHeight = 0;
            for(struct TreeNode* t=root; t; t=t->right) rHeight++;
            if(lHeight==rHeight-1) return (1<<rHeight)-1;
            else return (1 << lHeight)+countNodes(root->right);
        }
        else return (1 << rHeight) + countNodes(root->left);
    }

Log in to reply
 

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