前言

这么简单的 T4。

思路

只需要判断每个节点的子树是否为对称二叉树，然后计算该子树的节点个数就行了。

怎么判断是否为对称二叉树呢？先看一个图。

当到节点

x

时，需要满足

v_{l_x}=v_{r_x}

。到节点

y

和

z

时，需要满足

v_{l_y}=v_{r_z}

和

v_{r_y}=v_{l_z}

。若其中

l,r

其中一个的值为

-1

或

v

不相等，那么它就不是对称二叉树。

AC 代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,v[N],l[N],r[N],son[N];
bool dfs(int x,int y){
	if(x==-1&&y==-1) return true;//都是叶子节点时满足条件
	if(x==-1||y==-1) return false;//其中一个为叶子节点不满足
	if(v[x]!=v[y]) return false;//v值不同不满足
	return dfs(l[x],r[y])&&dfs(r[x],l[y]);
}
int count(int x){
	if(x==-1) return 0;
	son[x]=count(l[x])+count(r[x])+1;
	return son[x];
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&v[i]);
	for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
	count(1); //计算子树的节点个数
	int sum=0;
	for(int i=1;i<=n;i++) if(dfs(i,i)) sum=max(sum,son[i]);
	printf("%d\n",sum);
	return 0;
}

题解：P5018 [NOIP2018 普及组] 对称二叉树

文章操作

前言

思路

AC 代码

相关推荐

评论

题解：P5018 [NOIP2018 普及组] 对称二叉树