NOIP2018普及组第四题解析

这道题就比第三题好多了。。。

直接用暴力做法!

如果一个二叉树是对称的,那么对于深度相同的两个节点u,v,必定有lson(u)和rson(v),rson(u)和lson(v)。

因此我们就可以写出这一份看起来像是暴力的正解:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cctype>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int n,son[1000050][2],val[1000050],size[1000050];

//son[i][0]为i的左儿子
//son[i][1]为i的右儿子

inline void dfs(int u)
{
	size[u]=1;
	if (son[u][0]!=-1)
	{
		dfs(son[u][0]);
		size[u]+=size[son[u][0]];
	}
	if (son[u][1]!=-1)
	{
		dfs(son[u][1]);
		size[u]+=size[son[u][1]];
	}
}

inline bool check(int u,int v)
{
	if (u==-1 && v==-1)
		return true;
	if (u!=-1 && v!=-1 && val[u]==val[v] && check(son[u][0],son[v][1]) && check(son[u][1],son[v][0]))
		return true;
	return false;
}

int main()
{
	n=read();
	for (int i=1;i<=n;i++)
		val[i]=read();
	for (int i=1;i<=n;i++)
	{
		son[i][0]=read();
		son[i][1]=read();
	}
	dfs(1);
	int ans=0;
	for (int i=1;i<=n;i++)
		if (check(son[i][0],son[i][1]))
			ans=max(ans,size[i]);
	cout << ans << endl;
	return 0;
}

对于上面这份代码,很显然对于每一次check操作,当二叉树为完全二叉树的时候,时间复杂度最大,为树高

至于为什么非完全二叉树的时候更快呢?因为这个时候这棵二叉树是很容易不满足对称要求的,而不对称的又被我们剪枝掉了,因此会更快。

/*最后分享一下我在洛谷自测的成绩:

T1:100

T2:100

T3:50

T4:0

不知道有没有一等奖。*/

0 0 vote
Article Rating
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x