[C++知识库]1123 Is It a Complete AVL Tree (30 分)

AVL树的建立过程；
做的时候发现 判定高度的那个 if 只能写 = =2 或者 = =-2，不能写》2 或《-2；
然后就一个正常的判断完全二叉树。建个数组，存个最大索引，0到这个索引之间有空位置就说明不是完全二叉树。

#include<bits/stdc++.h>
using namespace std;
int n,ma=-1;
vector<int> v(30);
struct node{
	int val;
	node *l,*r;
};
node* ll(node *root){
	node *t=root->l;
	root->l=t->r;
	t->r=root;
	return t;
}
node* rr(node *root){
	node *t=root->r;
	root->r=t->l;
	t->l=root;
	return t;
}
node* lr(node *root){
		root->l=rr(root->l);
		return ll(root);
}
node* rl(node *root){
		root->r=ll(root->r);
		return rr(root);
}
int geth(node *root){
	if(root==NULL)
	return 0;
	return max(geth(root->l),geth(root->r))+1;
}
node* inser(node *root,int val){
	if(root==NULL){
		root=new node();
		root->val=val;
		root->l=root->r=NULL;
	}
	else if(val<root->val){
		root->l=inser(root->l,val);	
		if(geth(root->l)-geth(root->r)==2)
			val<root->l->val?root=ll(root):root=lr(root);
	}
	else{
		root->r=inser(root->r,val);
		if(geth(root->l)-geth(root->r)==-2)
		val<root->r->val?root=rl(root):root=rr(root);
	}
	return root;
}

void lev(node *root,int index){
	if(root==NULL)
	return ;
	ma=max(ma,index);
	v[index]=root->val;
	lev(root->l,2*index+1);
	lev(root->r,2*index+2);
}
int main(){
	cin>>n;
	node *root=NULL;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		root=inser(root,x);
	}
	lev(root,0);
	int f=1;
	for(int i=0;i<=ma;i++){
		if(v[i]!=0){
			if(i!=0)
			printf(" ");
			printf("%d",v[i]);
		}
		else
		f=0;
	}
	f==1?printf("\nYES\n"):printf("\nNO\n");;
	return 0;
}