AcWing 1616. 判断完全 AVL 树
原题链接
中等
作者:
xxxxuu
,
2021-08-21 08:36:27
,
所有人可见
,
阅读 253
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;
struct node{
int v,height;
node *lchild,*rchild;
};
int n,value;
unordered_map<node*,int> pos;
node* newnode(int v){ //建立一个新结点
node* temp=new node;
temp->v=v;
temp->height=1;
temp->lchild=temp->rchild=NULL;
return temp;
}
int getHeight(node* root){ //得到树高
if(root==NULL) return 0;
return root->height;
}
int getBalance(node* root){ //计算平衡因子
return getHeight(root->lchild)-getHeight(root->rchild);
}
void updateHeight(node* root){ //更新树的高度
root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}
//左旋
void L(node* &root){
node* temp=root->rchild;
root->rchild=temp->lchild;
temp->lchild=root;
updateHeight(root);
updateHeight(temp);
root=temp;
}
//右旋
void R(node* &root){
node*temp=root->lchild;
root->lchild=temp->rchild;
temp->rchild=root;
updateHeight(root);
updateHeight(temp);
root=temp;
}
//插入操作
void insert(node* &root,int v){
if(root==NULL){
root=newnode(v);
return;
}
if(v<root->v){
insert(root->lchild,v);
updateHeight(root);
if(getBalance(root)==2){
if(getBalance(root->lchild)==1){ //LL 根进行右旋
R(root);
}
else if(getBalance(root->lchild)==-1){ //LR 左孩子左旋再根右旋
L(root->lchild);
R(root);
}
}
}
else{
insert(root->rchild,v);
updateHeight(root);
if(getBalance(root)==-2){
if(getBalance(root->rchild)==-1){ //RR 根进行左旋
L(root);
}
else if(getBalance(root->rchild)==1){ //RL 右孩子右旋再根左旋
R(root->rchild);
L(root);
}
}
}
}
bool bfs(node* root){
queue<node*> q;
vector<int> layer;
q.push(root);
pos[root]=1;
bool res=true;
while(!q.empty()){
node* temp=q.front();
q.pop();
if(pos[temp]>n) res=false;
layer.push_back(temp->v);
if(temp->lchild!=NULL){
q.push(temp->lchild);
pos[temp->lchild]=pos[temp]*2;
}
if(temp->rchild!=NULL){
q.push(temp->rchild);
pos[temp->rchild]=pos[temp]*2+1;
}
}
cout<<layer[0];
for(int i=1;i<layer.size();i++) cout<<" "<<layer[i];
cout<<endl;
return res;
}
int main(){
node* root=NULL;
cin>>n;
for(int i=0;i<n;i++){
cin>>value;
insert(root,value);
}
bool res=bfs(root);
if(res==true) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}