模板类写法:
1.这种写法中，我把y总的bfs代码拆分成了dfs(之前做过的判断是否完全搜索二叉树)和bfs(普通的层序遍历)
2.整理了y总上课画的4中avl树模型

#include<bits/stdc++.h>
using namespace std;
const int N=21;
int n;
int l[N],r[N],v[N],h[N],q[N];
int idx=0;
int maxidx;
void update(int u)//更新此时这个结点的深度
{
    h[u]=max(h[l[u]],h[r[u]])+1;
}
void R(int &u)//引用类型要改变根
{
    int p=l[u];
    l[u]=r[p];//原先下一层的结点如果右边有子树，要挂在平衡过来根节点的左边
    r[p]=u;
    update(u),update(p);
    u=p;//将结点改为p
}
void L(int &u)
{
    int p=r[u];
    r[u]=l[p];
    l[p]=u;
    update(u),update(p);
    u=p;
}
int get_balance(int u)
{
    return h[l[u]]-h[r[u]];
}
void insert(int &u,int w)
{
    if(!u)
    {
        u=++idx;
        v[u]=w;
    }
    else if(v[u]>w)
    {
        insert(l[u],w);
        if(get_balance(u)==2)
        {
            if(get_balance(l[u])==1)//情况1
            {
                R(u);
            }
            else//情况3,先扭转u的左节点，扭成情况1
            {
                L(l[u]);
                R(u);
            }
        }
    }
    else 
    {
        insert(r[u],w);
        if(get_balance(u)==-2)
        {
           if(get_balance(r[u])==-1)//情况2
           {
                L(u);
           }
           else//情况4
           {
                R(r[u]);
                L(u);
           }
        }
    }
    update(u);//计算每个根的深度
}
void dfs(int u,int idx)
{
    if(u==0)
    {
        return ;
    }
    maxidx=max(maxidx,idx);
    dfs(l[u],idx*2);
    dfs(r[u],idx*2+1);
}
void bfs(int root)
{
    q[0]=root;
    int tt=0,hh=0;
    while(tt<=hh)
    {
        int t=q[tt++];
        if(l[t])
        {
            q[++hh]=l[t];
        }
        if(r[t])
        {
            q[++hh]=r[t];
        }
    }
}
int main()
{
    cin>>n;
    int root=0;
    for(int i=0;i<n;i++)
    {
        int w;
        cin>>w;
        insert(root,w);
    }
    dfs(root,1);
    bfs(root);
    for(int i=0;i<n;i++)
    {
        if(i!=n-1)
        {
            cout<<v[q[i]]<<" ";
        }
        else
        {
            cout<<v[q[i]]<<endl;
        }
    }
    if(maxidx==n)
    {
        cout<<"YES";
    }
    else
    {
        cout<<"NO";
    }
    return 0;
}