2018NOIP普及T4---对称二叉树

 题目 对称二叉树

　　
 　　题目描述

 

思路

　　检查是否符合对称条件

　　　　条件很简单——结构对称&&点权对称

　　　　要做到点权对称其实也就顺便结构对称了

　　　　于是条件可以简化为点权对称

　　　　可以考虑并行搜索

 1 bool con(int l,int r) {
 2     if(l == -1&&r == -1)
 3         return 1;
 4     if(l == -1||r == -1)
 5         return 0;
 6     if(w[l] == w[r])
 7         if(check(l,r))
 8             return 1;
 9     return 0;
10 }
11 bool check(int x,int y) {
12     if(x == -1&&y == -1)
13         return 1;
14     if(x == -1||y == -1)
15         return 0;
16     if(w[x] != w[y])
17         return 0;
18     int l = root[x].l,l1 = root[y].l;
19     int r = root[y].r,r1 = root[x].r;
20     if(con(l,r)&&con(l1,r1))
21         return 1;
22     return 0;
23 }

　　信仰深搜

　　　　就三个点

　　

　　　　你就装作上面还有一个点

　　

1 int dfs(int x) {
2     if(x == -1) return 0;
3     if(check(root[x].l,root[x].r)) {
4         int ans = find(x) + 1;
5         return ans;
6     }
7     int ans = max(dfs(root[x].l),dfs(root[x].r));
8     return ans;    
9 }

　　找答案

　　　　加一指根节点

1 int find(int x) {
2     int q = 0;
3     int l = root[x].l;
4     int r = root[x].r;
5     if(l != -1) q += find(l) + 1;
6     if(r != -1) q += find(r) + 1;
7     return q;
8 }

　　另外
　　　　读入时要记录这样几个玩意儿

　　

1     for(i = 1;i <= n;i++)
2         scanf("%d",&w[i]);
3     for(i = 1;i <= n;i++)
4         scanf("%d%d",&root[i].l,&root[i].r);   

　　code

　

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define m 1000001
 6 using namespace std;
 7 int w[m];
 8 struct n {
 9     int l,r;
10 }root[m];
11 bool con(int,int);
12 bool check(int,int);
13 //两个函数相互递归调用，并行搜索检查是否符合要求
14 int dfs(int);
15 //核心
16 int find(int);
17 //其实就是找有多少个点
18 int main() {
19     int i,n;
20     scanf("%d",&n);
21     for(i = 1;i <= n;i++)
22         scanf("%d",&w[i]);
23     for(i = 1;i <= n;i++)
24         scanf("%d%d",&root[i].l,&root[i].r);   
25     int ans = dfs(1);
26     printf("%d",ans);
27     return 0;
28 }
29 
30 bool con(int l,int r) {
31     if(l == -1&&r == -1)
32         return 1;
33     if(l == -1||r == -1)
34         return 0;
35     if(w[l] == w[r])
36         if(check(l,r))
37             return 1;
38     return 0;
39 }
40 bool check(int x,int y) {
41     if(x == -1&&y == -1)
42         return 1;
43     if(x == -1||y == -1)
44         return 0;
45     if(w[x] != w[y])
46         return 0;
47     int l = root[x].l,l1 = root[y].l;
48     int r = root[y].r,r1 = root[x].r;
49     if(con(l,r)&&con(l1,r1))
50         return 1;
51     return 0;
52 }
53 int find(int x) {
54     int q = 0;
55     int l = root[x].l;
56     int r = root[x].r;
57     if(l != -1) q += find(l) + 1;
58     if(r != -1) q += find(r) + 1;
59     return q;
60 }
61 int dfs(int x) {
62     if(x == -1) return 0;
63     if(check(root[x].l,root[x].r)) {
64         int ans = find(x) + 1;
65         return ans;
66     }
67     int ans = max(dfs(root[x].l),dfs(root[x].r));
68     return ans;    
69 }

 

总结

　　　　信仰很重要

　　　　这代码很慢但不至于卡常，还有大量可优化地方，此处不再赘述

　　　　它非常好理解，相信任何人都能写出比这更优秀的代码