PAT 甲级 1120-1123

1120 Friend Numbers (20分)

随便搞下就行了。

1121 Damn Single (25分)

需要注意以下细节的水题。

1122 Hamiltonian Cycle (25分)

哈密顿回路，暴力特判即可。

1123 Is It a Complete AVL Tree (30分)

$AVL$树的建立。

判断一个树是否为$CBT$，只需判断在一个节点没有子结点后，还会不会出现子结点，如果又出现了，则不是$CBT$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mst(a,b) memset(a,b,sizeof a)
struct node{
    int val;
    node *l,*r;
};
node* ro_L(node *rt){    //左旋操作 
    node* t=rt->r;
    rt->r=t->l;
    t->l=rt;
    return t;
}  
node* ro_R(node *rt){    //右旋操作 
    node * t=rt->l;
    rt->l=t->r;
    t->r=rt;
    return t;
}
node* ro_LR(node *rt){    //左旋后右旋操作 
    rt->l=ro_L(rt->l);
    return ro_R(rt);
}
node* ro_RL(node *rt){    //右旋后左旋操作 
    rt->r=ro_R(rt->r);
    return ro_L(rt);
}
int getht(node *rt) {
    if(!rt) return 0;
    return max(getht(rt->l), getht(rt->r)) + 1;
}
node *insert(node *rt, int val) {        //AVL 插入结点 
    if(!rt) {
        rt = new node();
        rt->val = val;
        rt->l=rt->r=NULL;
    } else if(val < rt->val) {
        rt->l=insert(rt->l, val);
        if(getht(rt->l)-getht(rt->r) == 2)
            rt=val<rt->l->val ? ro_R(rt) :ro_LR(rt);
                //LL:LR
    } else {
        rt->r = insert(rt->r, val);
        if(getht(rt->l) - getht(rt->r) == -2)
            rt = val > rt->r->val ?ro_L(rt) :ro_RL(rt);
            //RR:RL
    }
    return rt;
}
bool ok=1,jg=0;
void lev(node *rt){
    queue<node*>q;
    q.push(rt);int f=0;
    while(!q.empty()){
        node * u=q.front();q.pop();
        if(!f) printf("%d",u->val),f=1;
        else printf(" %d",u->val);
        if(u->l){
            if(jg) ok=0; 
            q.push(u->l);
        }
        else jg=1;
        if(u->r) {
            if(jg) ok=0;
            q.push(u->r);
        } else jg=1;
    }printf("\n");
}
int main(){
    int n;
    scanf("%d",&n);
    node* rt=NULL;
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        rt=insert(rt,x);
    }
    //printf("%d\n",rt->val);
    lev(rt); 
    puts(ok?"YES":"NO");
    return 0;
}