PAT1123 Is It a Complete AVL Tree

1123 Is It a Complete AVL Tree (30分)

题目链接
存一个模板，以后背这个

#include
using namespace std;
struct node{
    int data;
    node* left;
    node* right;
};
struct sq{int i,data;};
vector v;
bool cmp(sq& a,sq& b){return a.iright;
    tree->right=temp->left;
    temp->left=tree;
    return temp;
}
node* r(node* tree){
    node* temp=tree->left;
    tree->left=temp->right;
    temp->right=tree;
    return temp;
}
node* lr(node* tree){
    tree->left=l(tree->left);
    return r(tree);
}
node* rl(node* tree){
    tree->right=r(tree->right);
    return l(tree);
}
int height(node* tree){
    if(tree==NULL)return 0;
    int l=height(tree->left);
    int r=height(tree->right);
    return max(l,r)+1;
}
node* insert(node* tree,int v){
    if(tree==NULL){
        tree=new node();
        tree->data=v;
    }
    else if(vdata){
        tree->left=insert(tree->left,v);
        if(height(tree->left)-height(tree->right)>=2){
            if(vleft->data)tree=r(tree);
            else tree=lr(tree);
        }
    }
    else{
        tree->right=insert(tree->right,v);
        if(height(tree->right)-height(tree->left)>=2){
            if(v>tree->right->data)tree=l(tree);
            else tree=rl(tree);
        }
    }
    return tree;
}
void dfs(node* tree,int i){
    if(tree==NULL)return ;
    v.push_back({i,tree->data});
    dfs(tree->left,2*i);
    dfs(tree->right,2*i+1);
}
int main(){
    int n,i,m,judge=1;
    scanf("%d",&n);node* tree=NULL;
    for(i=0;i