【DFS】 【NOIP2018普及】对称二叉树_p5018 [noip2018 普及组] 对称二叉树

$Link$

$luoguP5018$

$Description$

一棵有点权的有根树如果满足以下条件，则被轩轩称为对称二叉树：

二叉树；
将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。
下图中节点内的数字为权值，节点外的 idid 表示节点编号。

现在给出一棵二叉树，希望你找出它的一棵子树，该子树为对称二叉树，且节点数 最多。请输出这棵子树的节点数。

注意：只有树根的树也是对称二叉树。本题中约定，以节点 T 为子树根的一棵“子 树”指的是：节点TT 和它的全部后代节点构成的二叉树。

$Input$ $and$ $Output$

$Sample$ $Input$ $1$

2 
1 3 
2 -1 
-1 -1 
1
2
3
4

$Sample$ $Output$ $1$

1
1

$Sample$ $Input$ $2$

10 
2 2 5 5 5 5 4 4 2 3 
9 10 
-1 -1 
-1 -1 
-1 -1 
-1 -1 
-1 2 
3 4 
5 6 
-1 -1 
7 8
1
2
3
4
5
6
7
8
9
10
11
12

$Sample$ $Output$ $2$

3
1

$Hint$

$Train$ $of$ $Thought$

直接暴力搜出以每一个点为根的子树的点的个数
然后判断是否对称即可

$Code$

#include<iostream>
#include<cstdio> 

using namespace std;

int n, ans;
int a[1000005], Tree_num[1000005], tree[1000005][2];

void dfs(int x)
{
	Tree_num[x]++;
	if (tree[x][1] != -1) {
		dfs(tree[x][1]);
		Tree_num[x] += Tree_num[tree[x][1]];
	}
	if (tree[x][0] != -1) {
		dfs(tree[x][0]);
		Tree_num[x] += Tree_num[tree[x][0]];
	}
}

bool check(int x, int y)
{
	if (x == -1 && y == -1) 
		return 1;//只有一个点的树
	if (x != -1 && y != -1 && a[x] == a[y]
	&& check(tree[x][0], tree[y][1])
	 && check(tree[x][1], tree[y][0]))//因为是对称，因此是左子树的右边对右子树的左边
	return 1;
	return 0;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d", &tree[i][0], &tree[i][1]);
	dfs(1);
	for (int i = 1; i <= n; ++i)
		if (check(tree[i][0], tree[i][1]))
			ans = max(ans, Tree_num[i]);
	printf("%d", ans);
}
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