题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805351302414336
题意：
给定n个树，依次插入一棵AVL树，按照层序遍历输出，最后判断这棵AVL树是不是完全二叉树。
思路：
这道题过段时间还要再来手搓一发。AVL模板要记住。
判断是不是完全二叉树的话只用看，如果有一个节点儿子是空，而他之后又出现了至少有一个儿子的节点的话，就不是完全二叉树。【蛮巧妙的】
#include<cstdio>
#include<cstdlib>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue> #define inf 0x7fffffff
using namespace std;
typedef long long LL;
typedef pair<string, string> pr; int n;
const int maxn = ;
vector<int>level[maxn];
typedef struct AvlNode{
int val;
AvlNode *left;
AvlNode *right;
int height;
}*AvlTree, AvlNode; int Max(AvlTree a, AvlTree b)
{
int x = , y = ;
if(a)x = a->height;
if(b)y = b->height;
if(x > y)return x;
else return y;
} AvlTree singleRotateWithRight(AvlTree T)
{
AvlTree L = T->left;
T->left = L->right;
L->right = T;
T->height = Max(T->left, T->right) + ;
L->height = Max(L->left, L->right) + ;
return L;
} AvlTree singleRotateWithLeft(AvlTree T)
{
AvlTree R = T->right;
T->right = R->left;
R->left = T;
T->height = Max(T->left, T->right) + ;
R->height = Max(R->left, R->right) + ;
return R;
} AvlTree doubleRotateWithLeft(AvlTree T)
{
T->left = singleRotateWithLeft(T->left);
return singleRotateWithRight(T);
} AvlTree doubleRotateWithRight(AvlTree T)
{
T->right = singleRotateWithRight(T->right);
return singleRotateWithLeft(T);
} AvlTree Insert(AvlTree T, int val)
{
if(T == NULL){
T = (AvlNode *)malloc(sizeof(struct AvlNode));
if(T){
T->val = val;
T->left = NULL;
T->right = NULL;
T->height = ;
}
}
else if(val < T->val){
T->left = Insert(T->left, val);
int l = , r = ;
if(T->left){
l = T->left->height;
}
if(T->right){
r = T->right->height;
}
if(l - r == ){
if(val < T->left->val){
T = singleRotateWithRight(T);
}
else{
T = doubleRotateWithLeft(T);
}
}
}
else if(val > T->val){
T->right = Insert(T->right, val);
int l = , r = ;
if(T->left)l = T->left->height;
if(T->right)r = T->right->height;
if(r - l == ){
if(val > T->right->val){
T = singleRotateWithLeft(T);
}
else{
T = doubleRotateWithRight(T);
}
}
}
T->height = Max(T->left, T->right) + ;
return T;
} bool after = false, iscomplete = true;
bool first = false;
void levelOrder(AvlTree T)
{
queue<AvlTree>que;
que.push(T);
while(!que.empty()){
AvlTree now = que.front();que.pop();
if(first)printf(" ");
else first = true;
printf("%d", now->val);
level[now->height].push_back(now->val);
if(now->left){
if(after)iscomplete = false;
que.push(now->left);
}
else{
after = ;
}
if(now->right){
if(after)iscomplete = false;
que.push(now->right);
}
else{
after = ;
}
}
} int main()
{
scanf("%d", &n);
AvlTree Tree = NULL;
for(int i = ; i < n; i++){
int x;
scanf("%d", &x);
Tree = Insert(Tree, x);
}
levelOrder(Tree);
printf("\n");
if(iscomplete)printf("YES\n");
else printf("NO\n");
return ;
}