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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
#include "stdlib.h"
#include <stdbool.h>

typedef struct Queue{
    struct TreeNode *node;
    struct Queue* next;
}Queue; //队列元素结构体

typedef struct Listqueue{
    Queue *front;
    Queue *last; 
}Listqueue;  //带头尾节点的队列

//入队
void Push_queue(struct TreeNode* tree, Listqueue *listqueue)
{
    Queue* time=malloc(sizeof(Queue));
    time->node=tree;
    time->next=NULL;
    if(listqueue->front==NULL)
    {
        listqueue->front=time;
        listqueue->last=time;
    }
    else 
    {
        listqueue->last->next=time;
        listqueue->last=time;
    }
}

//出队，并且返回一个队列元素
struct TreeNode* pop_queue(Listqueue* listqueue)
{
    if(listqueue->front==NULL)
        return NULL;
    else
    {
        Queue *time=malloc(sizeof(Queue));
        time=listqueue->front;
        listqueue->front=time->next;
        time->next=NULL;
        return time->node;
    }
}

//根据层序遍历判断该二叉树是否为完全二叉树
int cengxu_queue(struct TreeNode* tree)
{
    Listqueue* listqueue=malloc(sizeof(Listqueue));
    listqueue->front=NULL;
    listqueue->last=NULL;
    struct TreeNode* p=tree;
    int count_left=0,count_right=0; //当前结点的左右结点标志位
            //如果count_left=0,count_right=1,则不是完全二叉树……
    //标志位，意味着当前访问的二叉树结点是否违反完全二叉树的条件；
    int count=1; 

    while(p != NULL)
    {
        if(p->left != NULL)
        {
            Push_queue(p->left, listqueue);
            if(count==0)
                return 0;
            count_left=1;
        }
        else 
        {
            count_left=0;
            count=0;    //此时，层序遍历中不允许再出现新的结点
        }  
        if(p->right != NULL)
        {
            Push_queue(p->right, listqueue);
            if(count==0)
                return 0;
            count_right=1;
        }
        else 
        {
            count_right=0;
            count=0;    //此时，层序遍历中不允许再出现新的结点
        }
        p=pop_queue(listqueue);
    }
    return 1;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */
bool isCompleteTree(struct TreeNode* root ) {
    // write code here
    int i=cengxu_queue(root);
    //printf("--%d\n",i);
    return (i==1)? true:false;
}