这一题在T4让那些在T3翻车的小伙伴是望题流泪啊
其实这一题暴力的方法就可以做出来
通过枚举:
1)判断一下每一个结点为子树根节点的左右子树是否相等
2)时间复杂度,我们在check的时候,每一次树的大小增大一倍,那么在树有n个结点,我们每一个结点,最多logn次就可以了;所以枚举所有的结点,时间复杂度O(nlogn)可以接受
3)check是递归思想啦~~因为是二叉树嘛
4)深度遍历,求出子树的节点个数,最后输出结点个数最大的子树的结点编号即可
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
const int N = 1000005;
int siz[N],v[N],l[N],r[N],ans;
bool check(int r1,int r2){
if(v[r1]!=v[r2]) return false;
else if(r1==0&&r2==0) return true;
else return check(l[r1],r[r2])&&check(r[r1],l[r2]);
}
int dfs1(int rt){
if(!rt) return 0;
else return siz[rt] = dfs1(l[rt])+dfs1(r[rt])+1;
}
int dfs2(int rt){
if(!rt) return 0;
if(siz[l[rt]]==siz[r[rt]])
if(check(l[rt],r[rt])) ans = max(ans,siz[rt]);
dfs2(l[rt]);
dfs2(r[rt]);
}
int main(){
scanf("%d",&n);
for(int i = 1; i<=n; i++){
scanf("%d",&v[i]);
}
for(int i = 1; i<=n; i++){
scanf("%d%d",&l[i],&r[i]);
if(l[i]==-1)l[i] = 0;
if(r[i]==-1)r[i] = 0;
}
dfs1(1),dfs2(1);
printf("%d",ans);
}