1123 Is It a Complete AVL Tree
同类型题: pat:1066 输出AVL树最后的根结点
rebalancing is done to restore this property. :重新平衡是为了恢复这个属性
differ by at most one : 最多相差一个
水平遍历AVL树 并且判断这棵树是否是完整二叉树
判断是否是完整二叉树的方法:
判断每个结点的index是否是连续的
构建完树后,遍历一遍树, 将结点的index保存到vector v, 如果有点的index不存在 则不是完全二叉树
改进:
在水平遍历时,其实就可以判断是否是完全二叉树, 给每个结点赋值Index, 判断index是否与一个last相等
last为一个从0开始持续增长+1的变量
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
const int maxsize = 1 << 25;
struct Node {
Node* left, *right;
int val, h, index;
Node(int val): val(val), h(1), index(-1), left(nullptr), right(nullptr) {} //高度设置为1
} *root;
int getHeight(Node *root) { // 不用写为递归形势,因为插入元素时就是通过从底层向上层走
if(root == nullptr) return 0;
else
return root->h;
}
void updateHeight(Node *&root) {
root->h = max(getHeight(root->left), getHeight(root->right)) + 1;
}
int getFactor(Node *root) {
return getHeight(root->left) - getHeight(root->right);
}
void R(Node *&root) {
Node *temp = root->left; //
root->left = temp->right;
temp->right = root;
updateHeight(root); // 从底层向上更新高度
updateHeight(temp);
root = temp;
}
void L(Node *&root) {
Node *temp = root->right;
root->right = temp->left;
temp->left = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void insertTree(Node *&root, int val) {
if(root == nullptr) {
root = new Node(val);
return;
}
if(root->val > val) {
insertTree(root->left, val);
updateHeight(root); // 插入了元素后就需要重新更新插入元素上层的高度 (也不一定要在此位置更新, 可以在最后更新)
if(getFactor(root) == 2) {
if(getFactor(root->left) == 1) {
R(root);
} else {
L(root->left);
R(root);
}
}
} else {
insertTree(root->right, val);
updateHeight(root); // 插入了元素后就需要重新更新插入元素上层的高度
if(getFactor(root) == -2) {
if(getFactor(root->right) == -1) { // 判断右子树是否为-1 不要写为了root->left == -1
L(root);
} else {
R(root->right);
L(root);
}
}
}
}
void judgeCompleate(Node *&root, int index) {
if(root == nullptr) return;
v[index] = 1;
judgeCompleate(root->left, index * 2 + 1);
judgeCompleate(root->right, index * 2 + 2);
}
int main()
{
//Node *root = nullptr;
int n, val;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &val);
insertTree(root, val);
}
queue<Node*> q;
v.resize(1<<n);
judgeCompleate(root, 0);
bool isCompleate = true;
for(int i = 0; i < n; i++) {
if(v[i] == 0) isCompleate = false;
}
int cnt = 0;
q.push(root);
while(!q.empty()) {
Node* front = q.front();
q.pop();
printf("%s%d", cnt++ == 0 ? "" : " ", front->val);
if(front->left != nullptr) q.push(front->left);
if(front->right != nullptr) q.push(front->right);
}
printf("\n%s", isCompleate == false ? "NO" : "YES");
return 0;
}