NOIP2018 普及组 T4 对称二叉树

题目传送门

洛谷 P5018 [NOIP2018 普及组] 对称二叉树

算法解析

本题 DFS + 剪枝可过！！！

输入左儿子右儿子时如果遇到 $-1$ 就把它设为 $0$，这样好判断。

输入函数：

void inp() {
	scanf("%d", &n);
	
	for(int i = 1; i <= n; ++i)
		scanf("%d", &w[i]);
	
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &le[i], &rt[i]);
		
		if(le[i] == -1)
			le[i] = 0;
		if(rt[i] == -1)
			rt[i] = 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

然后计算出所有子树的结点个数，方便剪枝和更新答案：

void dfs1(int u) {
	if(!u)
		return;
	
	dfs1(le[u]);
	dfs1(rt[u]);
	
	cnt[u] = cnt[le[u]] + cnt[rt[u]] + 1;
}
1
2
3
4
5
6
7
8
9

然后就是计算答案了，我们先写一个函数 bool check(int u, int v)，就是判断以 $u$ 结点为根结点的子树和以 $v$ 结点为根结点的子树是否对称，这里有很多剪枝，但都很简单，相信大家都能看懂：

void bemax(int &a, int b) {
	a = a > b ? a : b;
}

bool check(int u, int v) {
	if(!u && !v)
		return true;
	
	if(!u || !v)
		return false;
	
	if(w[u] != w[v])
		return false;
	
	if(cnt[u] != cnt[v])
		return false;
	
	return check(le[u], rt[v]) & check(rt[u], le[v]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

有了这个函数，就很好计算答案了：

void dfs2(int u) {
	if(!u)
		return;
	
	if(check(le[u], rt[u]))
		bemax(ans, cnt[u]);
	
	dfs2(le[u]);
	dfs2(rt[u]);
}
1
2
3
4
5
6
7
8
9
10

最后再输出一下 $ans$ 就可以了，这样我们就 A（shui）掉了此题。

总代码

#include <cstdio>
using namespace std;

const int N = 1e6 + 5;

int n;
int w[N];
int le[N], rt[N];
int cnt[N];
int ans;

void bemax(int &a, int b) {
	a = a > b ? a : b;
}

bool check(int u, int v) {
	if(!u && !v)
		return true;
	
	if(!u || !v)
		return false;
	
	if(w[u] != w[v])
		return false;
	
	if(cnt[u] != cnt[v])
		return false;
	
	return check(le[u], rt[v]) & check(rt[u], le[v]);
}

void dfs1(int u) {
	if(!u)
		return;
	
	dfs1(le[u]);
	dfs1(rt[u]);
	
	cnt[u] = cnt[le[u]] + cnt[rt[u]] + 1;
}

void dfs2(int u) {
	if(!u)
		return;
	
	if(check(le[u], rt[u]))
		bemax(ans, cnt[u]);
	
	dfs2(le[u]);
	dfs2(rt[u]);
}

void inp() {
	scanf("%d", &n);
	
	for(int i = 1; i <= n; ++i)
		scanf("%d", &w[i]);
	
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &le[i], &rt[i]);
		
		if(le[i] == -1)
			le[i] = 0;
		if(rt[i] == -1)
			rt[i] = 0;
	}
}

void work() {
	dfs1(1);
	dfs2(1);
	printf("%d\n", ans);
}

int main() {
	inp();
	work();
	
	return 0;
}
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

提交记录

AC 记录

尾声

如果这篇博客对您（您的团队）有帮助的话，就帮忙点个赞，加个关注！

最后，祝您（您的团队）在 OI 的路上一路顺风！！！

┬┴┬┴┤・ω・)ノ Bye_Bye