欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-18 22:55:41
题目 对称二叉树 题目描述 思路 检查是否符合对称条件 条件很简单——结构对称&&点权对称 要做到点权对称其实也就顺便结构对称了 于是条件可以简化为点权对称 可以考虑并行搜索 信仰深搜 就三个点 你就装作上面还有一个点 找答案 加一指根节点 另外 读入时要记录这样几个玩意儿 code 总结 信仰很重 ......

 题目 对称二叉树

  
   题目描述

 

思路

  检查是否符合对称条件

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

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

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

    可以考虑并行搜索

 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 }

  信仰深搜

    就三个点

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

    你就装作上面还有一个点

  

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 }

 

总结

    信仰很重要

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

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