An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

## Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

## Output Specification:

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print YES if the tree is complete, or NO if not.

5
88 70 61 63 65

70 63 88 61 65
YES

## Sample Input 2:

8
88 70 61 96 120 90 65 68

## Sample Output 2:

88 65 96 61 70 90 120 68
NO

## 解答

#include<iostream>
#include<queue>

using namespace std;

struct node
{
int key;
struct node *lchild, *rchild;
};

int GetHeight(node *node) {
if (node == NULL) return 0;
int lh = GetHeight(node->lchild);
int rh = GetHeight(node->rchild);
return max(lh, rh) + 1;
}

void LevelOrder(node *root)
{
node *p = NULL;
queue<node*> nodes;
if (root == NULL) return;
nodes.push(root);
while (!nodes.empty()) {
p = nodes.front();
nodes.pop();
printf("%d", p->key);
if (p->lchild) {
nodes.push(p->lchild);
}
if (p->rchild) {
nodes.push(p->rchild);
}
if (nodes.empty()) printf("\n");
else printf(" ");
}
}

void IsComplete(node *root)
{
node *p = NULL;
bool complete = true;
bool nullTag = false;
queue<node*> nodes;
if (root == NULL) return;
int currentCount = 1;
nodes.push(root);
while (!nodes.empty()) {
p = nodes.front();
nodes.pop();
if (p == NULL) {
nullTag = true;
continue;
}
if (nullTag) complete = false;
nodes.push(p->lchild);
nodes.push(p->rchild);
}
if (complete) printf("YES");
else printf("NO");
}

node *leftRotate(node *root) {
node *temp = root->rchild;
root->rchild = temp->lchild;
temp->lchild = root;
return temp;
}
node *rightRotate(node *root) {
node *temp = root->lchild;
root->lchild = temp->rchild;
temp->rchild = root;
return temp;
}
node *rightLeftRotate(node *root) {
root->rchild = rightRotate(root->rchild);
return leftRotate(root);
}
node *leftRightRotate(node *root) {
root->lchild = leftRotate(root->lchild);
return rightRotate(root);
}
node *Insert(node *root, int key) {
if (root == NULL) {
root = new node();
root->key = key;
}
else if(root->key>key){
root->lchild = Insert(root->lchild, key);
int lh = GetHeight(root->lchild), rh = GetHeight(root->rchild);
if (lh - rh >= 2) {
// 左左
if (key < root->lchild->key) root = rightRotate(root);
//左右
else root = leftRightRotate(root);
}
}
else {
root->rchild = Insert(root->rchild, key);
int lh = GetHeight(root->lchild), rh = GetHeight(root->rchild);
if (rh - lh >= 2) {
// 右右
if (key > root->rchild->key) root = leftRotate(root);
// 右左
else root = rightLeftRotate(root);
}
}
return root;
}

int main()
{
int n, k;
cin >> n;
node *root(NULL);
node *tp = NULL;
for (int i = 0; i < n; i++) {
cin >> k;
root = Insert(root, k);
}
LevelOrder(root);
IsComplete(root);
return 0;
}