当前位置：首页 > news >正文

leetcode 958.二叉树的完全性检验

news 2025/7/8 2:42:19

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;}}
}