PAT 1123 Is It a Complete AVL Tree C++版

PAT 1123 Is It a Complete AVL Tree C++版

1.题意

给出一个整数列，判断由这个数列得到的平衡二叉树是否是一棵完全的平衡二叉树。

2.分析

主要分成两个步骤：

• step 1:得到一棵平衡二叉树
• step 2：判断是否完全
  第一部分在PAT中已经有题目（pat 1066）实现过了。第二部分也已经题目（记不清了）有实现过。简单的拼接一下即可。

3.代码

#include<cstdio>
#include<iostream>
#include<queue> 
#include<vector>
#define maxn 100

using namespace std;

struct Node{
	int data;
	int height;
	Node* left;	
	Node* right;
};

int N;
int arr[maxn];
queue<Node*> que;
vector<int> ans;


Node* newNode(int v){
	Node* node = new Node;//新建一个节点
	node->left = NULL;
	node->right = NULL;
	node->height = 1;//高度为1
	node->data = v;
	return node; 
}

//得到节点的高度 
int getHeight(Node* root){
	if(root == NULL) return 0;
	return root->height;
}

//得到该节点的平衡因子 [左子树-右子树]
int getBF(Node* root){
	return	getHeight(root->left) - getHeight(root->right); 
}

void updateHeight(Node* &root){
	root->height = max(getHeight(root->left),getHeight(root->right)) + 1;
} 

//左旋操作 
Node* L(Node* &root){
	Node* temp = root->right;
	root->right = temp->left;
	temp->left = root;
	updateHeight(root);
	updateHeight(temp);
	root = temp;
} 

Node* R(Node* &root){
	Node* temp = root->left;
	root->left = temp->right;
	temp->right = root;
	updateHeight(root);//注意是先对root更新，再对temp更新 
	updateHeight(temp);
	root = temp;	
}

void insert(Node* &root,int v){
	if(root == NULL){
		root = newNode(v);
		return ;
	}
	if(v < root->data){//进入左子树 
		insert(root->left,v);
		updateHeight(root);//更新节点的高度 
	//	cout << root->data <<",h="<<root->height<<"\n";
		if( getBF(root) == 2){//说明左子树比右子树高 
			if(getBF(root->left) == 1) {//LL型 
	//			cout <<"R(root)\n";
				R(root);//右旋 
			}
			else if(getBF(root->left) == -1) {//LR型 
				L(root->left);
				R(root); 
			}			
		}	
	}
	else{//创建右子树 
		insert(root->right,v);
		updateHeight(root); 
		if(getBF(root) == -2){//右子树高 
			if( getBF(root->right) == 1){//RL
				R(root->right);
				L(root);					
			} 
			else if(getBF(root->right) == -1){//RR
				L(root); 
			}			
		}
	}
}

void preOrder(Node* root) {	
	cout << root->data <<" ";
	if(root->left!=NULL) preOrder(root->left);	
	if(root->right!=NULL) preOrder(root->right); 	
}

//判断是否是一棵完全二叉树 
bool isCBT(Node* root){
	que.push(root);
	Node* temp;
	bool first = false;//第一次判断 
	bool flag = false; //最终的判断 
	while(!que.empty()){//当queue非空时 
		temp = que.front();
		ans.push_back(temp->data);
		
		if(temp->left!=NULL) que.push(temp->left);
		if(temp->right!=NULL) que.push(temp->right);
		if(temp->left==NULL && temp->right!=NULL) {
			flag = true;//修改标志		
		}
		if( (temp->left !=NULL || temp->right!=NULL) && first){
			flag = true;			
		} 
		if(temp->right == NULL && !first) {//说明之后就不应该再有子节点了 
			first = true;
		}
		que.pop();
	}
	return flag; 
}


int main(){
	cin >> N;
	int i,j;
	Node* root = NULL;
	for(i = 0;i< N;i++){
		cin >> arr[i];
		insert(root,arr[i]);
	}
	//preOrder(root);
	bool flag = isCBT(root);	
	for(i = 0;i< ans.size();i++) {
		if(i!=ans.size()-1) cout << ans[i]<<" ";
		else cout <<ans[i] <<"\n";
	} 
	if(!flag)	cout << "YES";
	else cout << "NO";
}

4.测试用例

3
88 70 61

5
88 70 61 63 65

5.执行结果

一遍AC啦，啦啦啦啦