判断是否是完全二叉树

╰+哭是因爲堅強的太久メ 2022-06-17 13:59 193阅读 0赞

判断是否是完全二叉树

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

**输入格式：**

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

**输出格式：**

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出“YES”，如果该树是完全二叉树；否则输出“NO”。

**输入样例1：**

38 45 42 24 58 30 67 12 51

**输出样例1：**

38 45 24 58 42 30 12 67 51

YES

**输入样例2：**

38 24 12 45 58 67 42 51

**输出样例2：**

38 45 24 58 42 12 67 51

#include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int f[1<<20];
    void build(int x,int y)
    {
        if(f[x]==0)
            f[x]=y;
        else if(y<f[x])
            build(x<<1|1,y);
        else
            build(x<<1,y);
    }
    int main()
    {
        int n,m,a;
        scanf("%d",&n);
        memset(f,0,sizeof(f));
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a);
            build(1,a);
        }
        int flag=0,k=1;
        for(int i=0; i<n; k++)
        {
            if(f[k])
            {
                printf("%d%c",f[k],i==n-1?'\n':' ');
                i++;
            }
            else
                flag=1;
        }
        if(flag)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
        return 0;
    }