对称二叉树

思路

• 1.先用结构体存树
• 2.对树进行dfs遍历，记录子树的大小
• 3.写一个check函数判断是否是对称二叉树

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,INF=0x3f3f3f3f;
typedef long long ll;

struct node{
    int v;
    int l,r;
    int size;
}tree[N];
int n,ans;

void dfs(int u){
    tree[u].size=1;
    if(tree[u].l!=-1){
        dfs(tree[u].l);
        tree[u].size+=tree[tree[u].l].size;
    }
    if(tree[u].r!=-1){
        dfs(tree[u].r);
        tree[u].size+=tree[tree[u].r].size;
    }
} 

bool check(int a,int b){
    if(a==-1&&b==-1) return true;
    if(a==-1) return false;
    if(b==-1) return false;
    if(tree[a].v!=tree[b].v) return false;
    if(check(tree[a].l,tree[b].r)&&check(tree[b].l,tree[a].r)){
        return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>tree[i].v;
    } 
    for(int i=1;i<=n;i++){
        cin>>tree[i].l>>tree[i].r;
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        if(check(tree[i].l,tree[i].r)) ans=max(ans,tree[i].size);
    }
    cout<<ans<<"\n";
    return 0;
}