注意事项：
- 插入后、旋转后要更新相应结点的高度
- 先更新子树高度、再更新结点高度
- 结点高度为该结点子树较高者高度+1
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int N;
vector<int> traversal;
struct node {
int val, height;
node *left, *right;
node(int v) {
val = v;
height = 1;
left = NULL;
right = NULL;
}
}*root = NULL;
int getHeight(node *p) {
return p == NULL ? 0 : p->height;
}
void updateHeight(node *&cur) {
cur->height = max(getHeight(cur->left), getHeight(cur->right)) + 1;
}
void L(node *&p) {
node *temp = p->right;
p->right = temp->left;
temp->left = p;
p = temp;
updateHeight(p->left); //特别注意更新结点高度
updateHeight(p);
}
void R(node *&p) {
node *temp = p->left;
p->left = temp->right;
temp->right = p;
p = temp;
updateHeight(p->right);
updateHeight(p);
}
void insert(node *&cur, int val) {
if (cur == NULL) {
cur = new node(val);
return;
}
if (cur->val > val) {
insert(cur->left, val);
if (getHeight(cur->left) - getHeight(cur->right) > 1) { //need adjustment
if (getHeight(cur->left->left) > getHeight(cur->left->right)) { //R
R(cur);
}
else {
L(cur->left);
R(cur);
}
}
}
else {
insert(cur->right, val);
if (getHeight(cur->right) - getHeight(cur->left) > 1) {
if (getHeight(cur->right->right) > getHeight(cur->right->left)) {
L(cur);
}
else {
R(cur->right);
L(cur);
}
}
}
updateHeight(cur);
}
int main() {
scanf("%d", &N);
for (int i = 0;i < N;i++) {
int temp;
scanf("%d", &temp);
insert(root, temp);
}
queue<node*> q;
q.push(root);
int level = 0;
bool isComplete = true;
while (!q.empty()) {
bool isFull = true, //标记当前层结点数是否满
isLastLevel = true, //标记当前层是否树的最后一层
isEnded = false; //对于某一层，标记各结点的子结点是否全部靠左
int count = q.size();
if(count != pow(2, level))
isFull = false;
for (int i = 0;i < count;i++) {
node *temp = q.front();
q.pop();
if (temp->left != NULL || temp->right != NULL)
isLastLevel = false;
traversal.push_back(temp->val);
if (temp->left != NULL) {
if (isEnded)
isComplete = false;
q.push(temp->left);
}
else isEnded = true;
if (temp->right != NULL) {
if (isEnded)
isComplete = false;
q.push(temp->right);
}
else isEnded = true;
}
if (!isFull && !isLastLevel)
isComplete = false;
level++;
}
for (int i = 0;i < traversal.size();i++) {
if (i != 0)
printf(" ");
printf("%d", traversal[i]);
}
if (isComplete)
printf("\nYES\n");
else printf("\nNO\n");
}