洛谷 P5018 对称二叉树

题目传送门

解题思路：

先计算每个点的子树有多少节点，然后判断每个子树是不是对称的，更新答案。

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 
 6 struct kkk{
 7     int l,r,v,len;
 8     kkk() {l = -1;r = -1;}
 9 }e[1000001];
10 int n,ans;
11 
12 bool solve(int ls,int rs) {
13     bool p = 1;
14     if(e[ls].v != e[rs].v) return false;
15     if((e[ls].l != -1 && e[rs].r == -1) || (e[ls].l == -1 && e[rs].r != -1) || (e[ls].r == -1 && e[rs].l != -1) || (e[ls].r != -1 && e[rs].l == -1)) return false;
16     if(e[ls].l != -1 && e[rs].r != -1)
17         p = p & solve(e[ls].l,e[rs].r);
18     if(e[ls].r != -1 && e[rs].l != -1)
19         p = p & solve(e[ls].r,e[rs].l);
20     return p;
21 }
22 
23 int dfs(int k) {
24     e[k].len = 1;
25     if(e[k].l != -1)
26         e[k].len += dfs(e[k].l);
27     if(e[k].r != -1)
28         e[k].len += dfs(e[k].r);
29     return e[k].len;
30 }
31 
32 int main(){
33     scanf("%d",&n);
34     for(int i = 1;i <= n; i++)
35         scanf("%d",&e[i].v);
36     for(int i = 1;i <= n; i++)    
37         scanf("%d%d",&e[i].l,&e[i].r);
38     dfs(1);
39     for(int i = 1;i <= n; i++)
40         if(solve(e[i].l,e[i].r))
41             ans = max(ans,e[i].len);
42     printf("%d",ans);
43     return 0;
44 }

//NOIP普及2018 T4