1616.判断完全平衡二叉树

本文主要是介绍1616.判断完全平衡二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

输入格式
第一行包含整数 N，表示插入序列中元素个数。第二行包含 N个不同的整数表示插入序列。

输出格式
第一行输出得到的AVL树的层序遍历序列。第二行，如果该AVL树是完全二叉树，则输出 YES，否则输出 NO。

数据范围
1≤N≤20

输入样例1：
5
88 70 61 63 65

输出样例1：
70 63 88 61 65
YES

输入样例2：
8
88 70 61 96 120 90 65 68

输出样例2：
88 65 96 61 70 90 120 68
NO

#include<iostream>
using namespace std;
const int N=25;
int l[N],r[N],h[N],v[N],idx; //左子树、右子树、树高、权值、第几个点
int n,root;
int q[N],hh,tt;//队列
int maxk,maxid;//判断完全二叉树
int hight(int u)
{return h[l[u]]-h[r[u]];
}
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;
}
void L(int &u)
{int p=r[u];r[u]=l[p],l[p]=u;update(u),update(p);u=p;
}
void insert(int &u,int w) //插入函数
{if(!u) u=++idx,v[u]=w;else if(w<v[u]) //插入到左子树{insert(l[u],w);if(hight(u)==2) {if(hight(l[u])==1) R(u); //LL型，右旋else L(l[u]),R(u); //LR型，先左旋再右旋}}else{insert(r[u],w);if(hight(u)==-2){if(hight(r[u])==-1) L(u); //RR型，左旋else R(r[u]),L(u);}}update(u);
}
void BFS(int u)//层序遍历
{q[hh++]=u;while(tt<hh){int k=q[tt++];if(l[k]) q[hh++]=l[k];if(r[k]) q[hh++]=r[k];cout<<v[k]<<" ";}
}
void check(int u,int k)
{if(!u) return;if(k>maxk){maxk=k;maxid=u;}check(l[u],2*k);check(r[u],2*k+1);
}
int main()
{cin>>n;for(int i=0;i<n;i++){int w;cin>>w;insert(root,w);}BFS(root); //层序遍历check(root,1); //判断是否为完全二叉树if(maxk==n) cout<<endl<<"YES";else cout<<endl<<"NO";return 0;
}