leetcode刷题日记:222. Count Complete Tree Nodes(完全二叉树的节点个数)

2024-01-03 06:47:14

这一道题,我们可以选择直接进行二叉树的遍历,将所有结点遍历一遍就能得到完全二叉树的结点个数,时间复杂度为O(n)。
代码如下:

int countNodes(struct TreeNode* root) {
    if(root==NULL){
        return 0;
    }
    return countNodes(root->left)+countNodes(root->right)+1;
}

运行结果截图:
在这里插入图片描述
但是我们注意到这是一颗完全二叉树,对于完全二叉树来说如果完全二叉树的层数为 L L L层那么完全二叉树的结点个数就在 [ 2 L , 2 L + 1 ? 1 ] [2^L , 2^{L+1}-1] [2L,2L+1?1]之间,所以我们先进行查找二叉树的层数,然后再在 [ 2 L , 2 L + 1 ? 1 ] [2^L , 2^{L+1}-1] [2L,2L+1?1]区间内进行二分查找,我们就能得到具体有多少个结点。
也就是说这一种方法的时间复杂度为 O ( l o g 2 n ? l o g 2 n ) O(log_2n*log_2n) O(log2?n?log2?n)这种时间复杂度比 O ( n ) O(n) O(n)更小。

int countNodes(struct TreeNode* root) {
    int depth = 0;
    struct TreeNode * p = root;
    while(p!=NULL){
        depth += 1;
        p = p->left;
    }
    if(depth>1){
        int left = 1<<(depth-1);
        int right = left*2 - 1;
        int *x = (int *)malloc(sizeof(int)*depth);
        while(left<=right){
            int n = 0;
            int middle = (left+right)/2;
            int middle1 = middle;
            while(middle!=0){
                x[n++] = middle;
                middle /= 2;
            }
            n--;
            p = root;
            while(n!=0){
                if(x[n]*2==x[n-1]){
                    p = p->left;
                }else{
                    p = p->right;
                }
                if(!p){
                    break;
                }
                n--;
            }
            if(!n){
                left = middle1+1;
            }else{
                right = middle1-1;
            }
        }
        return right;
    }else if(depth==1){
        return 1;
    }
    return 0;
}

运行结果截图:
在这里插入图片描述

文章来源:https://blog.csdn.net/apprentice_eye/article/details/134489813
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。