本文作者：Zhang, Xuheng
本文分类：编程学习笔记 浏览：1107
阅读时间：1160字, 约1.5-2分钟
这道题就比第三题好多了。。。
直接用暴力做法！
如果一个二叉树是对称的，那么对于深度相同的两个节点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
不知道有没有一等奖。*/
关于作者Zhang, Xuheng
- 还没有填写个人简介
- Email: hy23682@126.com
- 注册于: 2020-04-07 05:11:14