Yet another solution based on binary-search, the time complexity is easy to calculate.


  • 0
    B
    int countNodes(TreeNode* root) {
        if(root==nullptr) return 0;
        int depth=0;
        TreeNode * cur=root;
        while(cur){
            ++depth;
            cur=cur->left;
        }
        if(depth==1)
            return 1;
        --depth;
        int ans=(1<<depth)-1;
        int l=1, r=(1<<(depth-1))+1, mid;
        while(l<r){
            mid=(l+r)>>1;
            if(getSon(root, mid, depth-1)!=2){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        ans+=(l-1)*2;
        if(l!=(1<<(depth-1))+1)
            ans+=getSon(root, l, depth-1);
        return ans;
    }
    int getSon(TreeNode * rt, int l, int height){
        if(height==0){
            int ret=0;
            if(rt->left!=nullptr) ++ret;
            if(rt->right!=nullptr) ++ret;
            return ret;
        }
        int lson=(1<<(height-1));
        if(l<=lson)
            return getSon(rt->left, l, height-1);
        else
            return getSon(rt->right, l-lson, height-1);
    }

Log in to reply
 

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