【NOIP2018普及组】对称二叉树_2018普及组第四题

分析

就是一道 纯爆搜 （并且代码非常简洁）
不知道为什么放在第四题 被摆渡车卡了半天的我QAQ
先跑一遍dfs预处理出所有子树的大小sum[]
从1到n，以每一个节点为跟节点向下搜索，判断是否是对称二叉树，不断更新满足条件的最大sum[]值
设当前节点为x, l[x], r[x]分别代表当前节点的左右子节点

dfs(l[x],r[x])每个向下比较：
1.若两个子节点值都为-1则返回ture
2.若两个子节点值都不为-1且相等并且dfs(l[r[x]],r[l[x]])和dfs(r[l[x]],l[r[x]])返回值都为1 ，则返回ture
3.否则返回false

一句话概括：
如果这颗树是对称的，那么它的左子节点=右子节点，左子节点的右子节点=右子节点的左子节点……
依次向下寻找，然后递归 （其实画个图就非常清晰了）

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
int n,m,sum[N],l[N],r[N],a[N];
ll read(){
	ll sum=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar(); 
	}
	return sum*f;
}
void dfs(int x){
	sum[x]=1;
	if(l[x]!=-1){
		dfs(l[x]);
		sum[x]+=sum[l[x]];
	}
	if(r[x]!=-1){
		dfs(r[x]);
		sum[x]+=sum[r[x]];
	}
}
int check(int x,int y){
	if(x==-1&&y==-1)return 1;
	if(x!=-1&&y!=-1&&a[x]==a[y]&&check(l[x],r[y])&&check(r[x],l[y]))return 1;
	return 0;
}
int main(){
//	freopen("tree.in","r",stdin);
//	freopen("tree.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
	a[i]=read();
	for(int i=1;i<=n;i++)
	{
		l[i]=read();
		r[i]=read();
	}
	dfs(1);
	int ans=0;
    for(int i=1;i<=n;i++){
    	if(check(l[i],r[i]))
    	ans=max(ans,sum[i]);
	}
	cout<<ans;
	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