模拟(树形dp $O(n)$ 100pts)

• 设计判断两棵子树是否对称的结构
• 统计子树的节点数目
• 统计对称子树的节点的最大值

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct Tree{ //二叉树节点
    int l,r;
    int v;
}tr[N];
int s[N];
int ans=0;
bool check(int l,int r) //判断对称
{
    if(!l||!r) return !l&&!r; //如果有一个为空，则左右都是空为真
    if(tr[l].v!=tr[r].v) return false; //值不相等
    return check(tr[l].l,tr[r].r)&&check(tr[l].r,tr[r].l); //递归判断({左左,右右},{左右,右左})
}
int dfs1(int r) //统计每棵子树的节点数目
{
    if(r==0) return 0;
    s[r]=dfs1(tr[r].l)+dfs1(tr[r].r)+1;
    return s[r];
}
void dfs2(int r) //递归找对称子树的最大节点数
{
    if(r==0) return ;
    if(check(tr[r].l,tr[r].r)) //对称则更新答案
    {
        ans=max(ans,s[r]);
    }
    dfs2(tr[r].l); //递归计算左子树
    dfs2(tr[r].r); //递归计算右子树
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) //获取节点值
    {
        cin>>tr[i].v;
    }
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        if(l!=-1) tr[i].l=l;
        if(r!=-1) tr[i].r=r;
    }
    dfs1(1); //统计每棵子树的节点数目
    dfs2(1); //寻找对称节点的最大子树节点
    cout<<ans;
    return 0;
}