首页 > 试题广场 >

判断是不是完全二叉树

[编程题]判断是不是完全二叉树
  • 热度指数：85632 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树，确定他是否是一个完全二叉树。

完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）

数据范围：节点数满足
样例图1：
样例图2：
样例图3：

示例1

输入

{1,2,3,4,5,6}

输出

true
示例2

输入

{1,2,3,4,5,6,7}

输出

true
示例3

输入

{1,2,3,4,5,#,6}

输出

false

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
求offer的她很讲文明头像 求offer的她很讲文明 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */

#include <stdio.h>
bool isCompleteTree(struct TreeNode* root ) {
    // write code here
    if(root == NULL)
    {
        return true;
    }

    struct TreeNode *Queue[100];
    int front = 0;
    int rear = 0;

    Queue[rear++] = root;
    int flag = 1;

    struct TreeNode * node;
    while(front != rear)
    {
        node = Queue[front++];

        if(node->left)
        {
            if(flag == 0)
            {
                return false;
            }
            Queue[rear++] = node->left;
        }
        else {
            flag = 0;
        }

        if(node->right)
        {
            if(flag == 0)
            {
                return false;
            }
            Queue[rear++] = node->right;

        }
        else {
            flag = 0;
        }


    }

    return true;

}

发表于 2024-05-09 17:29:29 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿
一份漏洞百出的垃圾代码 
bool isCompleteTree(struct TreeNode* root ) {
    bool EmptyNodeFlag=false;
    struct TreeNode **p,*pbuffer1[10000]={NULL},*pbuffer2[10000]={NULL};
    int i, Treefloor;
    if(root==NULL)
        return true;
    if(root->right==NULL && root->left!=NULL) 
        if(root->left->left!=NULL || root->right!=NULL) 
            return false;
    
    p = pbuffer1;
    pbuffer1[0] = root;
    for(Treefloor=0;Treefloor<100;Treefloor++) {
        bool EmptyFloorFlag=true;   
        for(i=0;i<pow(2,Treefloor);i++) {
            if(p[i]!=NULL) {
                if(p==pbuffer1) {
                    pbuffer2[i*2] = p[i]->left;
                    pbuffer2[i*2+1] = p[i]->right;
                }
                else {
                    pbuffer1[i*2] = p[i]->left;
                    pbuffer1[i*2+1] = p[i]->right;
                }
                if(p[i]->left!=NULL || p[i]->right!=NULL)
                    EmptyFloorFlag = false;  
                if(p[i]->left==NULL) {
                    if(p[i]->right==NULL) 
                        EmptyNodeFlag=true;
                    else 
                        return false;
                }
                else {
                    if(p[i]->right==NULL) 
                            EmptyNodeFlag=true;
                    else {
                        if(EmptyNodeFlag==true)
                            return false;
                    }
                }
            }
            else 
                EmptyNodeFlag=true;
        }

        if(p==pbuffer1) 
            p=pbuffer2;
        else 
            p=pbuffer1;
        if(EmptyFloorFlag)
            break;
    }
    return true;   
}


编辑于 2024-03-16 22:08:06 回复(0)
C
202313160412马源江头像 202313160412马源江
我的方法就是笨办法
int max=0;
 int fg=0;
 int df;
 void jj(struct TreeNode*p,int leve)//找到最深度
 {
    if(p==NULL)return;
    if(max<leve)max=leve;
    jj(p->left,leve+1);
    jj(p->right,leve+1);
 }
 void jj2(struct TreeNode*p,int leve)//找到第二深度的数量
 {
    if(p==NULL)return;
    if(df==leve)fg++;
    jj2(p->left,leve+1);
    jj2(p->right,leve+1);
 }
 int qq(int num)//2的乘方函数
 {
     int a;
     int all=1;
     for(a=1;a<=num;a++)
     {
        all*=2;
     }
     return all;
 }
bool isCompleteTree(struct TreeNode* root ) {
    if(root->left==NULL&&root->right==NULL)return true;//单个根也是完全的
    else{
   jj(root,1);
   df=max-1;
   jj2(root,1);
   int b=qq(df-1);
   if(b!=fg)return false;//实际的第二深度数量与理论的不等就不可能是完全
   else{
   struct TreeNode*arr[100]; //广度优先搜索创建的队列
   int flag=0,flag2=0,basic=0,top=0;
   arr[top++]=root;//弹出一个把左右节点入队列
   while(basic<top)
   {
   if(root->left==NULL&&root->right!=NULL)//左无右有直接不可能
   {
    flag=1;
    break;
   }
   if(root->left!=NULL&&root->right!=NULL)//左右都有直接入
   {
    if(flag2!=1)//如果前面出现左有右无或左右都无，后续只能出现全无否则不可能
    {
    arr[top++]=root->left;
    arr[top++]=root->right;
    }
    else {
        flag=1;
        break;
    }
   }
   if(root->left==NULL&&root->right==NULL)flag2=1;
   if(root->left!=NULL&&root->right==NULL)
   {
       if(flag2!=1)//如果前面出现左有右无或左右都无，后续只能出现全无否则不可能
       {
        arr[top++]=root->left;
        flag2=1;
       }
       else {
               flag=1;
               break;      
       }
   }
   root=arr[++basic];
   }
    if(flag==1)return false;
   else return true;
   }
}
}
发表于 2024-03-09 20:03:26 回复(0)
C
芸某头像 芸某
感觉有点逃课的做法。。
正常思路应该是找个队列做层次遍历
但是既然节点数这么少的话。。。 
bool isCompleteTree(struct TreeNode* root ) {
    // write code here
    struct TreeNode* nodelist[300];
    nodelist[0] = root;
    int i,j;
    i = 0; j = 1;
    while(i<j){
        if(nodelist[i]==NULL){
            break;
        }
        nodelist[j++] = nodelist[i]->left;
        nodelist[j++] = nodelist[i]->right;
        i++;
    }
    while(i<j){
        if(nodelist[i++]!=NULL){
            return false;
        }
    }
    return true;
}


发表于 2023-09-23 18:57:35 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
bool isCompleteTree(struct TreeNode* root )
{
    // write code here
    struct TreeNode*T[50];
    int rear=0;
    int front=0;
    int depth=0;
    int flag=1;
    int count=0;
    T[front++]=root;
    T[front++]=NULL;
    while(front!=rear)
    {
        int F=1;
        root=T[rear];
        rear=(rear+1)%50;  
        if(count==pow(2,depth-1))
        {
            flag=1;
        }
        else
        {
            flag=0;
            if(0==count)
            {
                flag=1;
            }
        }
        count= (front-rear+50)%50;
        while(root)
        {
            int flag1=0;
            int flag2=0;
            if(!flag)
            {
                return false;
            }//一层未满下一层有结点
         
            if(root->left)
            {
                T[front]=root->left;
                front=(front+1)%50;
                flag1=1;
            }
            if(root->right)
            {
                T[front]=root->right;
                front=(front+1)%50;
                if(!flag1)
                {
                    return false;
                }//某个结点只有右孩子
                flag2=1;
            }
           
            if(!F&&(flag1||flag2))
            {
                return false;
            }
            if(!flag1||!flag2)
            {
                F=0;
            }
            //某层前面未满但后面还有结点
            root=T[rear];
            rear=(rear+1)%50;
        }
        depth++;
        if(front==rear)
        {
            break;
        }
        T[front]=NULL;
        front=(front+1)%50;
    }

    return true;
}
发表于 2023-06-27 11:44:19 回复(0)
C
碧秋头像 碧秋 
#define MAXQSIZE 32
typedef struct TreeNode TreeNode ;
bool isCompleteTree(struct TreeNode* root ) {
    TreeNode* queue[MAXQSIZE];//队列实现BFS
    TreeNode* r = root;
    TreeNode* node = NULL;
    int front = 0, rear = 0;
    int size;
    int flag = 0; //代表是否已经访问到空结点
    queue[rear] = r; //根节点入队
    rear = (rear + 1) % MAXQSIZE;
    while (front != rear) { //队不为空
        size = (rear - front + MAXQSIZE) % MAXQSIZE;
        while (size-- > 0) {
            node = queue[front];
            front = (front + 1) % MAXQSIZE;
            if (node == NULL)
                flag = 1;
            else { //当访问非空结点时发现前面已经访问过空结点
                if (flag == 1) return false;
                queue[rear] = node->left; //左孩子入队
                rear = (rear + 1) % MAXQSIZE;
                queue[rear] = node->right; //右孩子入队
                rear = (rear + 1) % MAXQSIZE;
            }//else
        }//while size
    }//while
    return true;
}

发表于 2023-03-09 13:20:18 回复(0)
C
牛客703418606号头像 牛客703418606号 
bool isCompleteTree(struct TreeNode* root ) {
    struct TreeNode **queue=(struct TreeNode*)malloc(sizeof(struct TreeNode*)*100);
    int f=-1,r=-1;
    queue[++r]=root;
    int flag=0;
    while(r!=f){
        struct TreeNode *k=queue[++f];
        if(k!=NULL){
            if(flag) return 0;
            queue[++r]=k->left;
            queue[++r]=k->right;
        }
        else{
            flag=1;
        }        
    }
    return flag;
}
采用层次遍历  送给考研的大家 C版本

发表于 2022-08-15 21:42:56 回复(2)
提交观点

问题信息

树 dfs 广度优先搜索(BFS)
难度：
8条回答 7928浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断是不是完全二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号