题目链接

AVL平衡二叉树

判断完全二叉树的方法：从上往下编号1~N，左孩子是父节点的2倍，右孩子是父节点的2倍加1，按照层序放入vector中，如果最后一个元素的索引不为节点的总数n，则说明这棵树不是完全二叉树。

#include<bits/stdc++.h>
using namespace std;
struct node{
	node* left;
	node* right;
	int data,height,index;
};
int getHeight(node* root){
	if(root == NULL) return 0;
	return root->height; 
}
int getBalanceFactor(node* root){
	return getHeight(root->left) - getHeight(root->right);
}
void updateHeight(node* root){
	root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
}
void L(node* &root){ //左旋 
	node* tmp = root->right;
	root->right =  tmp->left;
	tmp->left = root;
	updateHeight(root);
	updateHeight(tmp);
	root = tmp;
}
void R(node* &root){ //左旋 
	node* tmp = root->left;
	root->left =  tmp->right;
	tmp->right = root;
	updateHeight(root);
	updateHeight(tmp);
	root = tmp;
}
void insert(node* &r, int v){
	if(r == NULL){
		r = new node;
		r->data = v;
		r->height = 1;
		r->left = r->right = NULL;
	}else if(v < r->data){ //左子树 
		insert(r->left,v);
		updateHeight(r);
		if(getBalanceFactor(r)==2){
			if(getBalanceFactor(r->left)== 1){ //LL型 
				R(r); 
			}else if(getBalanceFactor(r->left)==-1){ //LR型 
				L(r->left);
				R(r);
			}
		} 
	}else { //右子树 
		insert(r->right, v);
		updateHeight(r);
		if(getBalanceFactor(r)==-2){
			if(getBalanceFactor(r->right)==1){ //RL型 
				R(r->right);
				L(r);
			}else if(getBalanceFactor(r->right)==-1){//RR型
				L(r); 
			} 
		}
	}
}
vector<node*> v;
void levelorder(node* root){
	queue<node*> q;
	root->index = 1;
	q.push(root);
	while(!q.empty()){
		node* tmp = q.front();
		q.pop();
		v.push_back(tmp);
		if(tmp->left != NULL){
			q.push(tmp->left);
			tmp->left->index = 2*tmp->index;
		}
		if(tmp->right != NULL){
			q.push(tmp->right);
			tmp->right->index = 2* tmp->index + 1;
		}
	}
	
}
int main(){
	int n,num;
	cin>>n;
	node* root = NULL;
	for(int i=0;i<n;i++){
		cin>>num;
		insert(root, num);
	}	
	levelorder(root);
	for(int i=0;i<v.size();i++){
		cout<<v[i]->data;
		if(i!=v.size()-1) cout<<" ";
		else cout<<endl;
	}
	if(v[v.size()-1]->index != n) cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
	return 0;
}