总时间限制: 1000ms 内存限制: 65535kB
描述
给定一棵二叉树，在二叉树上执行两个操作：
- 节点交换
把二叉树的两个节点交换。
- 前驱询问
询问二叉树的一个节点对应的子树最左边的节点。
输入
第一行输出一个整数 t (t <= 100)，代表测试数据的组数。
对于每组测试数据，第一行输入两个整数 n m，n 代表二叉树节点的个数，m 代表操作的次数。
随后输入 n 行，每行包含 3 个整数 X Y Z，对应二叉树一个节点的信息。X 表示节点的标识，Y 表示其左孩子的标识，Z 表示其右孩子的标识。
再输入 m 行，每行对应一次操作。每次操作首先输入一个整数 type。
当 type=1，节点交换操作，后面跟着输入两个整数 x y，表示将标识为 x 的节点与标识为 y 的节点交换。输入保证对应的节点不是祖先关系。
当 type=2，前驱询问操作，后面跟着输入一个整数 x，表示询问标识为 x 的节点对应子树最左的孩子。
1<=n<=100，节点的标识从 0 到 n-1，根节点始终是 0.
m<=100
输出
对于每次询问操作，输出相应的结果。
样例输入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 2
5 5
0 1 2
1 -1 -1
2 3 4
3 -1 -1
4 -1 -1
2 0
1 1 2
2 0
1 3 4
2 2
3 2
0 1 2
1 -1 -1
2 -1 -1
1 1 2
2 0
|
样例输出
思路
由输入用例可以知道，我们可以使用一个二维数组来储存这棵树 a[101][2]，然后剩余的操作就看代码吧
Code
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
| #include <bits/stdc++.h>
using namespace std;
int a[101][2] = {};
void createTree(int n) {
int index, ChildL, ChildR;
for(int i = 1; i <= n; ++i) {
cin >> index >> ChildL >> ChildR;
a[index][0] = ChildL;
a[index][1] = ChildR;
}
}
void swap(int x, int y, int n) {
pair<int, bool> pX, pY;
for(int i = 0; i < n ; ++i) {
if(x == a[i][0]) {
pX.first = i;
pX.second = 0;
break;
} else if(x == a[i][1]) {
pX.first = i;
pX.second = 1;
break;
}
}
for(int i = 0; i < n ; ++i) {
if(y == a[i][0]) {
pY.first = i;
pY.second = 0;
break;
} else if(y == a[i][1]) {
pY.first = i;
pY.second = 1;
break;
}
}
if(pX.second == 0) {
a[pX.first][0] = y;
} else {
a[pX.first][1] = y;
}
if(pY.second == 0) {
a[pY.first][0] = x;
} else {
a[pY.first][1] = x;
}
}
void findLeftestChildAndPrint(int beginP) {
while(a[beginP][0] != -1) {
beginP = a[beginP][0];
}
cout << beginP << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t, n, m, typ, x, y;
cin >> t;
for(int i = 1;i <= t; ++i) {
cin >> n >> m;
createTree(n);
for(int j = 1; j <= m; ++j) {
cin >> typ;
if(typ == 1) {
cin >> x >> y;
swap(x, y, n);
} else {
cin >> x;
findLeftestChildAndPrint(x);
}
}
}
}
|
