Re: [理工] [資演] 105-台大-資工-資演 對答案

看板Grad-ProbAsk作者時間7年前 (2017/01/26 15:06), 7年前編輯推噓2(2推 0噓 17→)
留言19則, 7人參與, 最新討論串2/2 (看更多)
http://imgur.com/a/F9MXj 4.a 的部分我的想法是做inorder traversal 用一個變數存拜訪到的值 每次拜訪時將值和此變數比較 若比變數值小就是false 否則更新此變數值 後拜訪的都比較大的話就傳true 這樣應該可以吧？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485414385.A.B97.html ※ 編輯: gary19941208 (140.112.25.105), 01/26/2017 15:12:28
→
01/26 15:11, , 1F
直接用inorder輸出到陣列，檢查是否由小到大
01/26 15:11, 1F
→
01/26 15:13, , 2F
題目說要用常數的額外空間，如果用陣列會是O(n)
01/26 15:13, 2F
→
01/26 15:20, , 3F
抱歉，沒看清楚題目
01/26 15:20, 3F
→
01/26 15:20, , 4F
我原code也忽略了 space的問題
01/26 15:20, 4F
→
01/26 15:22, , 5F
用父親跟兒子做比較，如果父親小於左兒子或大於右兒子
01/26 15:22, 5F
→
01/26 15:22, , 6F
但 為什麼比變數值小是false @@ inoder 不是LRD嗎
01/26 15:22, 6F
→
01/26 15:23, , 7F
哦沒事我想成前序搜尋
01/26 15:23, 7F
→
01/26 15:23, , 8F
inorder是LDR
01/26 15:23, 8F
→
01/26 15:24, , 9F
額 無視我的話 我把R想成root
01/26 15:24, 9F
→
01/26 15:25, , 10F
joe的方法不work
01/26 15:25, 10F
推
01/26 15:26, , 11F
我覺得原po可行
01/26 15:26, 11F
→
01/26 15:49, , 12F
想問一下不可行的原因QQ
01/26 15:49, 12F
→
01/26 15:54, , 13F
樓上的方法,左子樹的右兒子大於root就不對了
01/26 15:54, 13F
→
02/03 10:27, , 14F
3
02/03 10:27, 14F
→
02/03 10:27, , 15F
/ \
02/03 10:27, 15F
→
02/03 10:27, , 16F
2 4
02/03 10:27, 16F
→
02/03 10:27, , 17F
/ \
02/03 10:27, 17F
→
02/03 10:28, , 18F
1 5
02/03 10:28, 18F
推
02/05 18:15, , 19F
02/05 18:15, 19F
‣ 更多 gary19941208 的文章
文章代碼(AID): #1OYP_nkN (Grad-ProbAsk)
‣ 更多 gary19941208 的文章
文章代碼(AID): #1OYP_nkN (Grad-ProbAsk)