给定一个二叉树,确定他是否是一个完全二叉树。
完全二叉树的定义:若二叉树的深度为 h,除第 h 层外,其它各层的结点数都达到最大个数,第 h 层所有的叶子结点都连续集中在最左边,这就是完全二叉树。(第 h 层可能包含 [1~2h] 个节点)
数据范围:节点数满足
样例图1:
样例图2:
样例图3:
{1,2,3,4,5,6}
true
{1,2,3,4,5,6,7}
true
{1,2,3,4,5,#,6}
false
/** * 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; }
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; }
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; }
#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; }
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版本