judge_Complete_binary_tree.cpp

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
// 根据先序遍历判断是否是完全二叉树，输入-1表示null
struct TreeNode {
    int ch;
    struct TreeNode *left;
    struct TreeNode *right;
};
struct TreeNode* build() {
    int v;
    struct TreeNode *T;
    scanf("%d", &v);
    if (v == -1) T = NULL;
    else {
        T = (struct TreeNode *) malloc(sizeof(struct TreeNode));
        T->ch = v;
        T->left = build();
        T->right = build();
    }
    return T;
}
struct TreeNode *q[10001];
int bfs(struct TreeNode *root)
{

    int flag = 0;
    int top = 1,tail = 1;
    q[tail++] = root;
    if(root==NULL) return 1;
    while(top!=tail)
    {
        struct TreeNode *tmp = q[top++];
        if(flag && (tmp->left || tmp->right)) return 0; 
        if(tmp->left == NULL && tmp->right) return 0; //左子树为空，但右子树不为空
        if(tmp->left) q[tail++] = tmp->left; // 放入左子树
        if(tmp->right) q[tail++] = tmp->right; //放入右子树
        else flag = 1; // 无右子树时需要下次特判是否还有子树
    }
    return 1;
}
int main()
{
    struct TreeNode *T;
    memset(q, 0, sizeof(q));
    T = build();
    printf("%d", bfs(T));
}

/*
input:
1 2 -1 3 -1 -1 -1

output:
0
*/