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

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