TOP101题解 | bm35#判断是不是完全二叉树#
判断是不是完全二叉树
https://www.nowcoder.com/practice/8daa4dff9e36409abba2adbe413d6fae
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @author Senky * @date 2023.08.03 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1 * @brief 层序遍历二叉树,当遇到空节点的时候说明,当前是最后一层的最后一个节点,如果又遇到一个空节点说明不是完全二叉树 * * @param root TreeNode类 * @return bool布尔型 */ #include <stdbool.h> struct QueueNode { struct TreeNode* tree_node; struct QueueNode* next; }; struct Queue { struct QueueNode* front; struct QueueNode* rear; int length; }; //判空 bool QueueIsEmpty(struct Queue* queue) { return queue->length == 0; } //创建一个空队列 struct Queue* Queue_create() { struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue)); queue->front = queue->rear = NULL; queue->length = 0; return queue; } //入队 void Queue_in(struct Queue* queue, struct TreeNode* tree_node) { struct QueueNode* new_node = (struct QueueNode*)malloc(sizeof(struct QueueNode)); new_node->tree_node = tree_node; new_node->next = NULL; if(QueueIsEmpty(queue)) { queue->front = queue->rear = new_node; } else { queue->rear->next = new_node; queue->rear = new_node; } queue->length++; } //出队 struct TreeNode* Queue_out(struct Queue* queue) { struct QueueNode* temp = queue->front; struct TreeNode* tree = temp->tree_node; if(1 == queue->length) { queue->front = queue->rear = NULL; } else { queue->front = queue->front->next; } free(temp); queue->length--; return tree; } bool isCompleteTree(struct TreeNode* root ) { // write code here bool NULLnode = false; struct Queue* queue = Queue_create(); Queue_in(queue, root); //空树或者只有一个结点的树 if(QueueIsEmpty(queue) || ( (root->left == NULL) && (root->right) ) ) { return true; } while(!QueueIsEmpty(queue)) { struct TreeNode* temp_treeNode = Queue_out(queue); if(NULL == temp_treeNode) { //第一次出现空节点 NULLnode = true; } else { //第二次出现空结点 if (NULLnode == true) { return false; } //左右孩子入队 Queue_in(queue, temp_treeNode->left); Queue_in(queue, temp_treeNode->right); } } return true; }#TOP101#
TOP101-BM系列 文章被收录于专栏
系列的题解