常规的AVL树插入问题 这种题背就完事了

#include<bits/stdc++.h>
using namespace std;
struct AVLTreeNode{
    int data,height,num;
    AVLTreeNode *left,*right;
    AVLTreeNode(int value, AVLTreeNode *l=nullptr, AVLTreeNode *r=nullptr):data(value), height(0),left(l),right(r) {}
};
int getHeight(AVLTreeNode*r){
    return r==nullptr?0:r->height;
}
AVLTreeNode*findAVL(AVLTreeNode*root,int data){
    if (root==nullptr || root->data==data)
        return root;
    if (data < root->data)
        return findAVL(root->left, data);
    else
        return findAVL(root->right, data);
}

AVLTreeNode* leftLeftRotation(AVLTreeNode* root){
    AVLTreeNode* k1= root->left;
    root->left = k1->right;
    k1->right = root;
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    k1->height = max(getHeight(k1->left), root->height) + 1;
    return k1;
}
AVLTreeNode* rightRightRotation(AVLTreeNode* root){
    AVLTreeNode* k2= root->right;
    root->right = k2->left;
    k2->left = root;
    root->height = max( getHeight(root->left), getHeight(root->right)) + 1;
    k2->height = max( getHeight(k2->right), root->height) + 1;
    return k2;
}
AVLTreeNode* leftRightRotation(AVLTreeNode* root){
    root->left = rightRightRotation(root->left);
    return leftLeftRotation(root);
}
AVLTreeNode* rightLeftRotation(AVLTreeNode* root){
    root->right = leftLeftRotation(root->right);
    return rightRightRotation(root);
}
AVLTreeNode* insertNode(AVLTreeNode* &root, int data){
    if (root == nullptr)
        root = new AVLTreeNode(data);
    else if (data < root->data){
        root->left = insertNode(root->left, data);
        if (getHeight(root->left) - getHeight(root->right) == 2){
            if (data < root->left->data)
                root = leftLeftRotation(root);
            else
                root = leftRightRotation(root);
        }
    }else if (data > root->data){
        root->right = insertNode(root->right, data);
        if (getHeight(root->right) - getHeight(root->left) == 2){
            if (data > root->right->data)
                root = rightRightRotation(root);
            else
                root = rightLeftRotation(root);
        }
    }
    root->height = max( getHeight(root->left), getHeight(root->right)) + 1;
    return root;
}
bool levelOrder(AVLTreeNode*root){
    root->num=1;
    int last=0;
    bool complete=true;
    queue<AVLTreeNode*>q;
    q.push(root);
    while(!q.empty()){
        AVLTreeNode*r=q.front();
        q.pop();
        printf("%s%d",r->num!=1?" ":"",r->data);
        if(r->num==last+1)
            ++last;
        else
            complete=false;
        if(r->left!=nullptr){
            r->left->num=r->num*2;
            q.push(r->left);
        }
        if(r->right!=nullptr){
            r->right->num=r->num*2+1;
            q.push(r->right);
        }
    }
    return complete;
}
int main(){
    int N,a;
    scanf("%d",&N);
    AVLTreeNode*root=nullptr;
    for (int i=0;i<N;++i) {
        scanf("%d",&a);
        root=insertNode(root,a);
    }
    bool complete=levelOrder(root);
    printf("\n%s",complete?"YES":"NO");
    return 0;
}