关于c++:PAT甲级1123-Is-It-a-Complete-AVL-Tree

题目粗心

给定一颗均衡二叉树的插入序列，要求输入它的层序序列并判断是否为齐全二叉树。

算法思路

首先须要对该 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;
}