Fork me on GitHub

PAT(甲级)渡劫(二十四)-Root of AVL Tree (25)


PAT(甲级)渡劫(二十四)-Root of AVL Tree (25)

代码如下:

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
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
struct TreeNode{
int val;
TreeNode *left,*right;
TreeNode(int v):val(v),left(NULL),right(NULL){}
};

int height(TreeNode *r){
return r == NULL?0:max(height(r->left),height(r->right))+1;
}
TreeNode *lRotate(TreeNode *r){
TreeNode *p = r->right;
r->right = p->left;
p->left = r;
return p;
}

TreeNode *rRotate(TreeNode *r){
TreeNode *p = r->left;
r->left = p->right;
p->right = r;
return p;
}
TreeNode *lrRotate(TreeNode *r){
r->left = lRotate(r->left);
return rRotate(r);
}
TreeNode *rlRotate(TreeNode *r){
r->right = rRotate(r->right);
return lRotate(r);
}
TreeNode *insert(int val,TreeNode *r){
if(r == NULL) return new TreeNode(val);
if(r->val < val){
r->right = insert(val,r->right);
if(abs(height(r->left)-height(r->right)) > 1){
r = (r->right->val < val)?lRotate(r):rlRotate(r);
}
}else{
r->left = insert(val,r->left);
if(abs(height(r->left)-height(r->right)) > 1){
r = (r->left->val > val)?rRotate(r):lrRotate(r);
}
}
return r;
}

int main(){
freopen("in.txt","r",stdin);
TreeNode *r = NULL;
int n;
scanf("%d",&n);
for(int i = 0 ; i < n ; i++){
int val;
scanf("%d",&val);
r = insert(val,r);
}
printf("%d\n",r->val);
return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%