作者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/m.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