题目粗心
给定一颗均衡二叉树的插入序列，要求输入它的层序序列并判断是否为齐全二叉树。
算法思路
首先须要对该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;}