题目链接
这道题是一道还行的深搜练手题,空间想象能力要足够。
题意要求的是求最大的子树节点数量,由题意给出的对称二叉树的定义,我们可以得出这样一种做法:先深搜一遍预处理出每个节点的子树大小,然后我们可以挨个遍历节点来判断当前节点的子树是否为对称二叉树,如果是,那么则通过当前节点子树大小来更新答案,然后就可以了。
check的过程如下:
参数为任意两个节点的编号,如果都为-1那么可以往上返回真;
如果check出两个节点都不为-1,且权值相同,那么可以继续将他们的左右儿子互换比对————注意是互换,即a节点的左儿子和b节点的右儿子来比,另外两个儿子同理。
图形自己窝懒所以没画……麻烦看官自己动手画一下吧……抱歉了……

代码

#include<cstdio>
using namespace std;
inline int read()
{
    int neg=1,x=0;
    char ch;
    while((ch=getchar())<'0'||ch>'9')
    {
        if(ch=='-')
            neg=-1;
    }
    x=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        x=x*10+(ch-'0');
    return x*neg;
}//快读
int n,sum[1000005],ans;
struct ecs
{
    int dat;
    int ls;
    int rs;
}sz[1000005];//结构体存每个点

inline bool cmp(int cp1,int cp2)
{
    if(cp1==-1&&cp2==-1)
    {
        return true;
    }//都莫得
    if((cp1!=-1&&cp2!=-1)&&(sz[cp1].dat==sz[cp2].dat))//注意当其中任何一个等于-1的时候特判一下,不然就RE了
    {
        if((cmp(sz[cp1].ls,sz[cp2].rs)&&cmp(sz[cp1].rs,sz[cp2].ls)))
            return true;
    }
    return false;
}
inline void dfs(int cur)
{
    sum[cur]=1;//初始化为每个节点子树大小至少为1
    if(sz[cur].ls!=-1)
    {
        dfs(sz[cur].ls);
        sum[cur]+=sum[sz[cur].ls];
    }
    if(sz[cur].rs!=-1)
    {
        dfs(sz[cur].rs);
        sum[cur]+=sum[sz[cur].rs];
    }
    //printf("ans\n");
}//通过深搜来判断每个节点的子树大小
inline int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    n=read();
    for(register int i=1;i<=n;i++)
    {
        sz[i].dat=read();
    }
    for(register int i=1;i<=n;i++)
    {
        sz[i].ls=read(),sz[i].rs=read();
    }
    dfs(1);
    for(register int i=1;i<=n;i++)
    {
        if(cmp(sz[i].ls,sz[i].rs))
        {
            ans=max(ans,sum[i]);
        }
    }
    printf("%d",ans);
    return 0;
}