【题意】
略
【解法】
暴力+剪枝
说实话一拿到题目最开始的想法是中序和中序对称、前序和后序对称，然而最后上手去写以后发现这编程复杂度高到一定境界，还是暴力拯救世界的好
首先，怎么判定一棵子树是不是对称二叉树
1 bool check(ll x,ll y) 2 { 3 if (x==-1&&y==-1) return true; // 皆为空 4 if (x==-1||y==-1) return false; // 一边不为空 5 if (a[x]!=a[y]) return false; // 数值不相等 6 return ((check(l[x],r[y])&&check(r[x],l[y]))); 7 }
如果待判定的子树的根节点为x，则只需要check(l[x],r[x])即可
然而对每个节点都判断，很显然是时间上是来不及的
需要剪枝
什么情况下完全不可能有对称二叉树
1、两棵子树节点数不同
2、两棵子树高度不同
3、两棵子树权值和/最大值/最小值不同
1 void dfs(ll rt,ll&h,ll&sz,ll&sum) 2 { // 节点，高度，节点数，权值和 3 if (rt<=0) 4 { 5 h=0,sz=0,sum=0; 6 return; 7 } 8 ll h1,h2,sz1,sz2,sm1,sm2; 9 dfs(l[rt],h1,sz1,sm1); 10 dfs(r[rt],h2,sz2,sm2); 11 if (h1==h2&&sz1==sz2&&sm1==sm2) 12 if (check(l[rt],r[rt])) 13 ans=max(ans,sz1+sz2+1); 14 h=max(h1,h2)+1; 15 sz=sz1+sz2+1; 16 sum=sm1+sm2+a[rt]; 17 }
实际上，只需要判断高度+节点数就行
【代码】
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1000000+5; 4 typedef long long ll; 5 ll n; 6 ll l[N]={0},r[N]={0}; 7 ll a[N]; 8 ll ans; 9 bool check(ll x,ll y) 10 { 11 if (x==0&&y==0) return true; // 皆为空 12 if (a[x]!=a[y]) return false; 13 return ((check(l[x],r[y])&&check(r[x],l[y]))); 14 } 15 void dfs(ll rt,ll&h,ll&sz) 16 { 17 if (rt<=0) 18 { 19 h=0,sz=0; 20 return; 21 } 22 ll h1,h2,sz1,sz2; 23 dfs(l[rt],h1,sz1); 24 dfs(r[rt],h2,sz2); 25 if (h1==h2&&sz1==sz2) 26 if (check(l[rt],r[rt])) 27 ans=max(ans,sz1+sz2+1); 28 h=max(h1,h2)+1; 29 sz=sz1+sz2+1; 30 } 31 int main() 32 { 33 scanf("%lld",&n); 34 for (int i=1;i<=n;i++) 35 scanf("%lld",&a[i]); 36 for (int i=1;i<=n;i++) 37 { 38 scanf("%lld%lld",&l[i],&r[i]); 39 if (l[i]==-1) l[i]++; 40 if (r[i]==-1) r[i]++; 41 } 42 a[0]=-1; 43 ans=1; 44 ll h,sz; 45 dfs(1,h,sz); 46 printf("%lld",ans); 47 }
