2018NOIP普及T4---对称二叉树
2018-12-02 06:12:22来源:博客园 阅读 ()
题目 对称二叉树
题目描述
思路
检查是否符合对称条件
条件很简单——结构对称&&点权对称
要做到点权对称其实也就顺便结构对称了
于是条件可以简化为点权对称
可以考虑并行搜索
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【NOIP2015普及组】 推销员(纪中数据-标准) 2019-08-16
- 牛客NOIP普及组R1 C括号(dp) 2018-09-10
- 1009 产生数 2002年NOIP全国联赛普及组 2018-06-17
- 1316 文化之旅 2012年NOIP全国联赛普及组 2018-06-17
- 1008 选数 2002年NOIP全国联赛普及组 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash