1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5struct TreeNode {
6    int val;
7    struct TreeNode *left;
8    struct TreeNode *right;
9};
10
11struct QueueNode {
12    struct TreeNode* node;
13    struct QueueNode* next;
14};
15
16struct Queue {
17    struct QueueNode* front;
18    struct QueueNode* rear;
19};
20
21struct Queue* createQueue() {
22    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
23    q->front = q->rear = NULL;
24    return q;
25}
26
27void enqueue(struct Queue* q, struct TreeNode* node) {
28    struct QueueNode* temp = (struct QueueNode*)malloc(sizeof(struct QueueNode));
29    temp->node = node;
30    temp->next = NULL;
31    if (q->rear == NULL) {
32        q->front = q->rear = temp;
33        return;
34    }
35    q->rear->next = temp;
36    q->rear = temp;
37}
38
39struct TreeNode* dequeue(struct Queue* q) {
40    if (q->front == NULL)
41        return NULL;
42    struct QueueNode* temp = q->front;
43    q->front = q->front->next;
44    if (q->front == NULL)
45        q->rear = NULL;
46    struct TreeNode* node = temp->node;
47    free(temp);
48    return node;
49}
50
51bool isQueueEmpty(struct Queue* q) {
52    return q->front == NULL;
53}
54
55bool isCompleteTree(struct TreeNode* root) {
56    if (root == NULL) return true;
57    struct Queue* q = createQueue();
58    enqueue(q, root);
59    bool encounteredNull = false;
60    while (!isQueueEmpty(q)) {
61        struct TreeNode* current = dequeue(q);
62        if (current == NULL) {
63            encounteredNull = true;
64        } else {
65            if (encounteredNull) return false;
66            enqueue(q, current->left);
67            enqueue(q, current->right);
68        }
69    }
70    return true;
71}

1function