对称二叉树

对称二叉树

• 分析

  也没什么好说的。看个图。
  
  对于一个节点来说，如果他对称，那么他的每一个节点都一一对应。
  
  于是只要跑一遍每一个点及其子树，判断一下每个节点与其对应的节点是否相等(值相等，且子树大小相等)就行了

• 代码

#include<bits/stdc++.h>

#define ls(u) ch[0][u]
#define rs(u) ch[1][u]

using namespace std;

const int N=1e6+10;

int n,ans,tot;
int v[N],ch[2][N],siz[N];

inline void dfs(int now)
{
    if(now==-1) return ;
    siz[now]=1;

    dfs(ls(now)),dfs(rs(now));

    siz[now]+=siz[ls(now)]+siz[rs(now)];
}

inline bool check(int x,int y)
{
    if(x==-1&&y==-1) return 1;
    if(x==-1||y==-1) return 0;
    if(siz[x]!=siz[y]) return 0;
    if(v[x]!=v[y]) return 0;

    if(check(ch[0][x],ch[1][y])&&check(ch[1][x],ch[0][y])) return 1;
    return 0;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&v[i]);
    for (int i=1;i<=n;i++) scanf("%d%d",&ls(i),&rs(i));

    dfs(1);

    for (int i=1;i<=n;i++)
        if(check(ch[0][i],ch[1][i])) ans=max(ans,siz[i]);

    printf("%d\n",ans);

    return 0;
}