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

2018-12-02 06:12:22来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

 题目 对称二叉树

  
   题目描述

 

思路

  检查是否符合对称条件

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

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

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

    可以考虑并行搜索

 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 }

 

总结

    信仰很重要

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

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

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:函数的重载(1)

下一篇:【LeetCode】Reverse Nodes in k-Group(k个一组翻转链表)