网站制作定制图,东莞公共资源交易中心,网站建设方案书可自行撰写,游戏网站开发有限公司1.题目要求:
给你一棵二叉树的根节点 root #xff0c;请你判断这棵树是否是一棵 完全二叉树 。在一棵 完全二叉树 中#xff0c;除了最后一层外#xff0c;所有层都被完全填满#xff0c;并且最后一层中的所有节点都尽可能靠左。最后一层#xff08;第 h 层#xff09;…1.题目要求:
给你一棵二叉树的根节点 root 请你判断这棵树是否是一棵 完全二叉树 。在一棵 完全二叉树 中除了最后一层外所有层都被完全填满并且最后一层中的所有节点都尽可能靠左。最后一层第 h 层中可以包含 1 到 2h 个节点。 2.题目代码:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*///创建队列
typedef struct queue{struct TreeNode* data;struct queue* next;
}queue_t;
//入队
void push(queue_t** head,struct TreeNode* data){queue_t* newnode (queue_t*)malloc(sizeof(queue_t));newnode-data data;newnode-next NULL;if(*head NULL){*head newnode;return;}queue_t* tail *head;while(tail-next ! NULL){tail tail-next;}tail-next newnode;
}
//出队
struct TreeNode* pop(queue_t** head){struct TreeNode* x (*head)-data;(*head) (*head)-next;return x;
}
bool isCompleteTree(struct TreeNode* root) {int node_count 0;//设置结点个数int* level_travel_node (int*)malloc(sizeof(int) * 200);//记录最后一层的标记数组int j 0;int depth 0;queue_t* quence NULL;int count 1;int nextcount 0;int size 0;//层序遍历开始push(quence,root);size;node_count;while(size ! 0){depth;for(int i 0;i count;i){struct TreeNode* temp pop(quence);size--;if(temp-left ! NULL){push(quence,temp-left);size;node_count;nextcount;}if(temp-right ! NULL){push(quence,temp-right);size;node_count;nextcount;}}count nextcount;nextcount 0;}//判断结点数如果节点数为1则直接返回trueif(node_count 1){return true;}else{//如果节点数不为1则判断结点总数是否符合完全二叉树的结点范围不符合直接返回falseif(node_count (int)pow(2,depth -1)node_count ((int)pow(2,depth) - 1)){printf(%d ,node_count);int depth_t 0;size 0;count 1;int remove_line_count 0;//记录除最后一行的节点数量nextcount 0;push(quence,root);size;remove_line_count;//再次进行层序遍历一直遍历到倒数第二次位置while(size ! 0){depth_t;//判断是否为倒数第二层 if(depth_t ! depth - 1){for(int i 0;i count;i){struct TreeNode* temp pop(quence);size--;if(temp-left ! NULL){push(quence,temp-left);size;remove_line_count;nextcount;}if(temp-right ! NULL){push(quence,temp-right);size;remove_line_count;nextcount;}}count nextcount;nextcount 0;}else{//是倒数第二层后把最后一层的结点进行记录如果为空为-1不为空为1for(int i 0;i count;i){struct TreeNode* temp pop(quence);size--;if(temp-left ! NULL){level_travel_node[j] 1;j;}else{level_travel_node[j] -1;j;}if(temp-right ! NULL){level_travel_node[j] 1;j;}else{level_travel_node[j] -1;j;}}break;}}//判断除最后一层的结点数量如果不对则返回falseif(remove_line_count ! ((int)pow(2,depth - 1) - 1)){return false;}else{int i 0;for(i 0;i j;i){if(level_travel_node[i] -1){break;}}//如果-1后的结点有1则为错如果不是则为trueint j_1 i 1;for(j_1 i 1;j_1 j;j_1){if(level_travel_node[j_1] 1){return false;}}return true;}}else{return false;}}
}解题步骤都在代码里了虽然比较繁琐但如果大家觉得好的话可以给个免费的赞吗谢谢了^ _ ^
