思路：
考察的点是建立AVL树以及如何判断是否为满二叉树。
建立AVL树需要搞清楚LL、LR、RR、RL四种情况如何左旋和右旋，如下：
| 类型 | BF条件 | 操作 |
|---|---|---|
| LL | BF(root)=2,BF(root->lchild)=1 | root右旋 |
| LR | BF(root)=2,BF(root->lchild)=-1 | 先root->lchild左旋，再root右旋 |
| RR | BF(root)=-2,BF(root->rchild)=-1 | root左旋 |
| RL | BF(root)=-2,BF(root->rchild)=1 | 先root->rchild右旋，再root左旋 |
接着是用bfs遍历判断是否为满二叉树：
按照层序遍历的方式（但遇到空结点也需要放入队列），将各个结点放入队列中，直到从队列拿出来的结点是空的。按照完全二叉树的定义，只有最后一层才能是有空结点，并且结点朝左排列。如果我们此时依次将队列前部的空结点全部拿出，队列应该最后是空的，此时证明是完全二叉树的。
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
struct node {
int data;
int height;
node* lchild;
node* rchild;
};
int getHeight(node* tnode)
{
if (tnode == NULL) return 0;
else return tnode->height;
}
void UpdateHeight(node* tnode)
{
tnode->height = max(getHeight(tnode->lchild), getHeight(tnode->rchild)) + 1;
}
int getBF(node* tnode)
{
return getHeight(tnode->lchild) - getHeight(tnode->rchild);
}
void L(node*& tnode)
{
node* temp = tnode->rchild;
tnode->rchild = temp->lchild;
temp->lchild = tnode;
UpdateHeight(tnode);
UpdateHeight(temp);
tnode = temp;
}
void R(node*& tnode)
{
node* temp = tnode->lchild;
tnode->lchild = temp->rchild;
temp->rchild = tnode;
UpdateHeight(tnode);
UpdateHeight(temp);
tnode = temp;
}
node* newnode(int v)
{
node* tnode = new node;
tnode->data = v;
tnode->height = 1;
tnode->lchild = tnode->rchild = NULL;
return tnode;
}
void insert(node*& root, int v)
{
if (root == NULL)
{
root = newnode(v);
return;
}
if (v < root->data)
{
insert(root->lchild, v);
UpdateHeight(root);
if (getBF(root) == 2)
{
if (getBF(root->lchild) == 1)
{
R(root);
}
else if (getBF(root->lchild) == -1)
{
L(root->lchild);
R(root);
}
}
}
else
{
insert(root->rchild, v);
UpdateHeight(root);
if (getBF(root) == -2)
{
if (getBF(root->rchild) == -1)
{
L(root);
}
else if (getBF(root->rchild) == 1)
{
R(root->rchild);
L(root);
}
}
}
}
node* create()
{
int n;
cin >> n;
node* root = NULL;
for (int i = 0; i < n; i++)
{
int t;
cin >> t;
insert(root, t);
}
return root;
}
void bfs(node* root)
{
vector<int> res;
queue<node*> q;
node* t;
q.push(root);
while (!q.empty())
{
t = q.front();
q.pop();
res.emplace_back(t->data);
if (t->lchild) q.push(t->lchild);
if (t->rchild) q.push(t->rchild);
}
for (int i = 0; i < res.size(); i++)
if (i == 0) cout << res[0];
else cout << " " << res[i];
cout << endl;
}
void checkCompleteBinary(node* root)
{
queue<node*> q;
node* t;
q.push(root);
while (!q.empty())
{
t = q.front();
q.pop();
if (t == NULL) break;
q.push(t->lchild);
q.push(t->rchild);
}
while (!q.empty() && q.front() == NULL)
q.pop();
if (q.empty()) cout << "YES";
else cout << "NO";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
node* root = create();
bfs(root);
checkCompleteBinary(root);
return 0;
}
