NC21472（对称二叉树）

感受

思路

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int lson[maxn], rson[maxn];
int val[maxn], n, num[maxn];
int ans;
void dfs(int u){
    num[u] = 1;
    if(lson[u] > 0){
        dfs(lson[u]); num[u] += num[lson[u]];
    }
    if(rson[u] > 0){
        dfs(rson[u]); num[u] += num[rson[u]];
    }
}
bool check(int u, int v){
    if(u == -1 && v == -1) return true;
    if(u == -1 || v == -1) return false;
    if(val[u] != val[v]) return false;
    return check(lson[u], rson[v]) && check(rson[u], lson[v]);
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &lson[i], &rson[i]);
    }
    dfs(1);
    for(int i = 1; i <= n; i++){
        if(check(lson[i], rson[i])){
            ans = max(ans, num[i]);
        }
    }
    printf("%d\n", ans);
    return 0;
}