题解 | #判断是不是完全二叉树#
判断是不是完全二叉树
https://www.nowcoder.com/practice/8daa4dff9e36409abba2adbe413d6fae
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ #include "stdlib.h" #include <stdbool.h> typedef struct Queue{ struct TreeNode *node; struct Queue* next; }Queue; //队列元素结构体 typedef struct Listqueue{ Queue *front; Queue *last; }Listqueue; //带头尾节点的队列 //入队 void Push_queue(struct TreeNode* tree, Listqueue *listqueue) { Queue* time=malloc(sizeof(Queue)); time->node=tree; time->next=NULL; if(listqueue->front==NULL) { listqueue->front=time; listqueue->last=time; } else { listqueue->last->next=time; listqueue->last=time; } } //出队,并且返回一个队列元素 struct TreeNode* pop_queue(Listqueue* listqueue) { if(listqueue->front==NULL) return NULL; else { Queue *time=malloc(sizeof(Queue)); time=listqueue->front; listqueue->front=time->next; time->next=NULL; return time->node; } } //根据层序遍历判断该二叉树是否为完全二叉树 int cengxu_queue(struct TreeNode* tree) { Listqueue* listqueue=malloc(sizeof(Listqueue)); listqueue->front=NULL; listqueue->last=NULL; struct TreeNode* p=tree; int count_left=0,count_right=0; //当前结点的左右结点标志位 //如果count_left=0,count_right=1,则不是完全二叉树…… //标志位,意味着当前访问的二叉树结点是否违反完全二叉树的条件; int count=1; while(p != NULL) { if(p->left != NULL) { Push_queue(p->left, listqueue); if(count==0) return 0; count_left=1; } else { count_left=0; count=0; //此时,层序遍历中不允许再出现新的结点 } if(p->right != NULL) { Push_queue(p->right, listqueue); if(count==0) return 0; count_right=1; } else { count_right=0; count=0; //此时,层序遍历中不允许再出现新的结点 } p=pop_queue(listqueue); } return 1; } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ bool isCompleteTree(struct TreeNode* root ) { // write code here int i=cengxu_queue(root); //printf("--%d\n",i); return (i==1)? true:false; }