Home PAT 1123 Is It a Complete AVL Tree
Post
Cancel

PAT 1123 Is It a Complete AVL Tree

Link

Yet another AVL 模板题 :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int n,a;
bool flag=true;
struct node{
    int val;
    struct node *left,*right;
};
int getHeight(node *root){
    if(root==NULL) return 0;
    return max(getHeight(root->left),getHeight(root->right))+1;
}
node* rotateLeft(node *root){
    node *p=root;
    root=p->right;
    p->right=root->left;
    root->left=p;
    return root;
}
node* rotateRight(node *root){
    node *p=root;
    root=p->left;
    p->left=root->right;
    root->right=p;
    return root;
}
node* rotateLeftRight(node *root){
    root->left=rotateLeft(root->left);
    return rotateRight(root);
}
node* rotateRightLeft(node *root){
    root->right=rotateRight(root->right);
    return rotateLeft(root);
}
node* Insert(node *root,int val){
    if(root==NULL){
        root=new node();
        root->val=val;
        root->left=root->right=NULL;
    }else if(val<root->val){
        root->left=Insert(root->left,val);
        if(getHeight(root->left)==getHeight(root->right)+2){
            if(getHeight(root->left->left)+1==getHeight(root->left->right)) root=rotateLeftRight(root);
            else root=rotateRight(root);
        }
    }else{
        root->right=Insert(root->right,val);
        if(getHeight(root->right)==getHeight(root->left)+2){
            if(getHeight(root->right->left)==getHeight(root->right->right)+1) root=rotateRightLeft(root);
            else root=rotateLeft(root);
        }
    }
    return root;
}
void levelOrder(node *root){
    queue<pair<node*,int>>q;
    printf("%d",root->val);
    int index=1;
    if(root->left) q.push({root->left,index<<1});
    if(root->right) q.push({root->right,(index<<1)+1});
    while(!q.empty()){
        node *p=q.front().first;
        index=q.front().second;
        if(index>n) flag=false;
        q.pop();
        printf(" %d",p->val);
        if(p->left) q.push({p->left,index<<1});
        if(p->right) q.push({p->right,(index<<1)+1});
    }
    printf("\n");
    printf("%s\n",flag?"YES":"NO");
}
// void DFS(node *root,int index){
//     if(index>20){
//         flag=false;
//         return;
//     }
//     if(root->left) DFS(root->left,index<<1);
//     if(root->right) DFS(root->right,(index<<1)+1);
// }
int main() {
    scanf("%d",&n);
    node *root=NULL;
    for(int i=1;i<=n;++i){
        scanf("%d",&a);
        root=Insert(root,a);
    }
    levelOrder(root);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.