一种解法

本题的做法就是：暴力+剪枝

说实话一拿到题目最开始的想法是中序和中序对称、前序和后序对称，然而最后上手去写以后发现这编程复杂度高到一定境界，还是暴力拯救世界的好！

首先，怎么判定一棵子树是不是对称二叉树？

bool check(ll x,ll y) { if (x==-1&&y==-1) return true; // 皆为空 if (x==-1||y==-1) return false; // 一边不为空 if (a[x]!=a[y]) return false; // 数值不相等 return ((check(l[x],r[y])&&check(r[x],l[y]))); }

如果待判定的子树的根节点为x，则只需要check(l[x],r[x])即可。

然而对每个节点都判断，很显然是时间上是来不及的，那么就需要剪枝了。

什么情况下完全不可能有对称二叉树

1、两棵子树节点数不同

2、两棵子树高度不同

3、两棵子树权值和/最大值/最小值不同

void dfs(ll rt,ll&h,ll&sz,ll&sum) { // 节点，高度，节点数，权值和 if (rt<=0) { h=0,sz=0,sum=0; return; } ll h1,h2,sz1,sz2,sm1,sm2; dfs(l[rt],h1,sz1,sm1); dfs(r[rt],h2,sz2,sm2); if (h1==h2&&sz1==sz2&&sm1==sm2) if (check(l[rt],r[rt])) ans=max(ans,sz1+sz2+1); h=max(h1,h2)+1; sz=sz1+sz2+1; sum=sm1+sm2+a[rt]; }

实际上，只需要判断高度+节点数就行

#include <bits/stdc++.h> using namespace std; const int N = 1000000+5; typedef long long ll; ll n; ll l[N]={0},r[N]={0}; ll a[N]; ll ans; bool check(ll x,ll y) { if (x==0&&y==0) return true; // 皆为空 if (a[x]!=a[y]) return false; return ((check(l[x],r[y])&&check(r[x],l[y]))); } void dfs(ll rt,ll&h,ll&sz) { if (rt<=0) { h=0,sz=0; return; } ll h1,h2,sz1,sz2; dfs(l[rt],h1,sz1); dfs(r[rt],h2,sz2); if (h1==h2&&sz1==sz2) if (check(l[rt],r[rt])) ans=max(ans,sz1+sz2+1); h=max(h1,h2)+1; sz=sz1+sz2+1; } int main() { scanf("%lld",&n); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); for (int i=1;i<=n;i++) { scanf("%lld%lld",&l[i],&r[i]); if (l[i]==-1) l[i]++; if (r[i]==-1) r[i]++; } a[0]=-1; ans=1; ll h,sz; dfs(1,h,sz); printf("%lld",ans); }