作者ihatetomato (茄茄)
看板C_and_CPP
标题[问题] Tree Travesal 题目理解问题
时间Thu Aug 24 15:13:33 2017
问题(Question):
第一次在本版发问请多包涵
如有不当之处请告知我自删~
最近在自学资料结构刷清大的OJ
在写一题level order traversal的题目的时候
不是很理解他题目想要的排序是什麽
这是题目
http://140.114.86.238/problem/10926/
用他的范例测资测我的code会给出一样的答案
但是可能他给的测资是只有两层的结构
若有三层或许我有理解上的错误
假设我给的资料如下
喂入的资料(Input):
1
8 3
2 4
1 6
1 8
1 3
3 2
3 5
7 2
预期的正确结果(Expected Output):
那依照我预期的正确排序结果是长这样
3 1 2 5 6 8 4 7
因此ouput是7
理由是觉得因为他建树的方式
是两个两个nodes建 并没有先後顺序的感觉 也就是分支没有谁左谁右
我於是就依照他说的小的孩子放左
小的孩子的孩子们也是照数值小的放左
错误结果(Wrong Output):
但我交出去不ac 显示为wrong answer
不知道他希望该有的排序会是如何
程式码(Code):(请善用置底文网页, 记得排版)
https://codepad.remoteinterview.io/AQUTQTEERA
想要问一下大家对这个题目的看法~谢谢!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.134.56.111
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1503558817.A.E61.html
1F:→ bluesoul: 一层一层从root往下,数字小的先走 08/24 17:11
2F:→ ihatetomato: 我试试看好了 感谢 不懂为何题目不这样写有点混淆 08/24 17:20
3F:→ bluesoul: 试试看把子节点先排序 08/24 17:25
4F:推 libertyleave: 题目的确写得不好 Level order 应该是要一层一层走 08/24 18:25
5F:→ libertyleave: 跟每个 node 有多少 children 关系不太, 我想他要 08/24 18:25
6F:→ libertyleave: 给一个图画清楚才比较好 08/24 18:27
7F:推 yvb: 把你的测资, 7 2 改为 7 4 测看看; 然後 7 4 移到 2 4 前再测 08/24 18:27
8F:推 libertyleave: 不过我觉得你这个测资输出应该要对呀 08/24 18:30
9F:→ libertyleave: 除非题目要的是每一层数字小的先走 但这跟 level 08/24 18:31
10F:→ libertyleave: order 的定义有点冲突 08/24 18:31
11F:→ libertyleave: 喔 那个测资是你的例子吗 那你的思路是没错的 08/24 18:36
12F:推 stucode: 你的想法是没错的 编号小的放左边 然後再LOT 08/24 18:40
13F:→ ihatetomato: 嗯嗯我原本也这样想 但是我试了各种测资输出来都 08/24 18:43
14F:→ ihatetomato: 是我预期的答案 但是却一直不ac 08/24 18:43
15F:推 libertyleave: 我看连结的程式跟测资跑出来的答案是错的 08/24 18:45
16F:→ libertyleave: 目前是4 我觉得应该是7 08/24 18:45
17F:→ ihatetomato: 那个4不知道是否是被修改过 我用clion跑是7 08/24 18:47
19F:→ stucode: 试试1 6 1 2 3 4 5 1 6 6 3 5 2 正确是4 你的跑出来是5 08/24 18:59
20F:推 libertyleave: 1 4 1 4 3 3 2 2 1 也是错的 08/24 19:00
21F:→ ihatetomato: 非常感谢~可能还有哪处有bug@@ 我再找找 08/24 19:02
22F:→ ihatetomato: 已AC~谢谢帮忙~ 08/24 20:32