题解 | #判断是不是完全二叉树#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */
typedef struct queue {
    struct TreeNode* data[100];
    int size;
} queue;
queue* init_queue1() {
    queue* my_queue = (queue*)malloc(sizeof(queue));
    if (my_queue == NULL) {
        return NULL;
    }
    for (int i = 0; i < 100; i++) {
        my_queue->data[i] = NULL;
    }
    my_queue->size = 0;
    return my_queue;
}
void push_queue1(queue* my_queue, struct TreeNode* data) {
    if (my_queue == NULL) {
        return;
    }
    my_queue->data[my_queue->size] = data;
    my_queue->size++;
}
struct TreeNode* pop_queue1(queue* my_queue) {
    if (my_queue == NULL || my_queue->size == 0) {
        return NULL;
    }
    struct TreeNode* value = my_queue->data[0];
    for (int i = 0; i < my_queue->size - 1; i++) {
        my_queue->data[i] = my_queue->data[i + 1];
    }
    my_queue->size--;
    return value;
}
bool isEmpty1(queue* my_queue) {
    if (my_queue == NULL || my_queue->size == 0) {
        return true;
    }
    return false;
}
bool isCompleteTree(struct TreeNode* root) {
    // write code here
    if (root == NULL) {
        return false;
    }
    struct TreeNode* node = root;
    queue* my_queue = init_queue1();
    push_queue1(my_queue, root);
    bool flag = false;//设立一个“哨兵”
    while (!isEmpty1(my_queue)) {
        node = pop_queue1(my_queue);
        if (flag) {
            if (!(node->left == NULL && node->right == NULL)) {//判断后面的节点是否为叶子节点
                return false;
            }
        }
        if (node->left != NULL) {
            push_queue1(my_queue, node->left);
            if (node->right == NULL) {//左节点不空，右节点为空，那么后面的节点必为叶子节点
                flag = true;
            }
        } else {
            if (node->right != NULL) {//左节点为空，右节点不空，一定不是完全二叉树
                return false;
            }
            flag = true;//否则后面的节点必要为叶子节点
        }
        if (node->right != NULL) {
            push_queue1(my_queue, node->right);
        }
    }
    return true;
}