题目粗心
给定一颗均衡二叉树的插入序列,要求输入它的层序序列并判断是否为齐全二叉树。
算法思路
首先须要对该 AVL 树进行建树操作 (具体不细说,看代码即可),而后对该树进行层序遍历,一边输入层序变量序列,一遍判断该树是否是齐全二叉树
判断二叉树是否是齐全二叉树的办法为:
- 1、如果以后节点只有右孩子,肯定不是。
- 2、如果以后节点有孩子,然而其前驱节点中存在孩子缺失的状况,那么肯定不是。
提交后果
AC 代码
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
struct Node {
int v;
Node *left;
Node *right;
int height;
};
int n;
// 生成新的结点
Node *newNode(int v) {
Node *w = new Node;
w->v = v;
w->height = 1;
w->left = nullptr;
w->right = nullptr;
return w;
}
int getHeight(Node *root) {if (root == nullptr) {return 0;} else {return root->height;}
}
int getBalancedFactor(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 *temp = root->right;
root->right = temp->left;
temp->left = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void R(Node *&root) {
Node *temp = root->left;
root->left = temp->right;
temp->right = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void insert(Node *&root, int x) {if (root == nullptr) {root = newNode(x);
return;
}
if (root->v < x) {insert(root->right, x);
// 插入实现后得得更新 root 的高度
updateHeight(root);
if (getBalancedFactor(root) == -2) {if (getBalancedFactor(root->right) == -1) {
//RR 型须要对 root 左旋一次
L(root);
} else if (getBalancedFactor(root->right) == 1) {
// RL 型,先对 root->right 右旋,再对 root 左旋
R(root->right);
L(root);
}
}
} else {insert(root->left, x);
// 插入实现后得得更新 root 的高度
updateHeight(root);
if (getBalancedFactor(root) == 2) {if (getBalancedFactor(root->left) == 1) {
// LL 型须要对 root 右旋一次
R(root);
} else if (getBalancedFactor(root->left) == -1) {
// LR 型,先对 root->left 左旋,再对 root 右旋
L(root->left);
R(root);
}
}
}
}
Node *createTree(int data[]) {
Node *root = nullptr;
for (int i = 0; i < n; ++i) {insert(root, data[i]);
}
return root;
}
bool isComplete = true;
bool onlyLeft = false;// 记录前驱是否只有左孩子
bool noChildren = false;// 记录前驱是否没有孩子
int num = 0;// 打印管制
void layerOrder(Node *root) {
queue<Node *> q;
q.push(root);
bool flag1 = false, flag2 = false;
while (!q.empty()) {Node *t = q.front();
q.pop();
printf("%d", t->v);
if (num < n - 1) {printf(" ");
} else {printf("\n");
}
++num;
if (t->left) {q.push(t->left);
}
if (t->right) {q.push(t->right);
}
// 判断是否是齐全二叉树
if (t->left == nullptr && t->right != nullptr) {
// 只有右孩子
isComplete = false;
} else if(noChildren||onlyLeft){if(t->left != nullptr||t->right != nullptr){
// 前驱呈现只有左孩子或者没有孩子的状况,以后节点还有孩子
isComplete = false;
}
} else if (t->left == nullptr && t->right == nullptr){
// 没有孩子
noChildren = true;
} else if(t->left != nullptr && t->right == nullptr){
// 只有左孩子
onlyLeft = true;
}
}
}
int main() {scanf("%d", &n);
int data[n];
for (int i = 0; i < n; ++i) {scanf("%d", &data[i]);
}
Node *root = createTree(data);
layerOrder(root);
if (isComplete) {printf("YES");
} else {printf("NO");
}
return 0;
}