[問題] ancestry problem

看板Prob_Solve作者 (精裝版喔)時間17年前 (2007/06/20 14:49), 編輯推噓2(2推 0噓 5→)
留言7則, 3人參與, 最新討論串1/15 (看更多)
給一顆 binary tree， 問某個 node 是不是另一個 node 的 ancestor， 要在 constant time 決定。 允許 O(n) 的 preprocessing。 n: # of node 我做了幾次嚐試都失敗，至少要logn， 3 種 traversal，也看不出什麼線索。 thanks -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.115.235.76
→
06/20 15:03, , 1F
想到一個，traversal時要對node encoding，不知是不是
06/20 15:03, 1F
→
06/20 15:04, , 2F
正解
06/20 15:04, 2F
推
06/20 15:39, , 3F
via suffix tree ?
06/20 15:39, 3F
→
06/20 15:39, , 4F
encoding 是否也是 logn 的一種?
06/20 15:39, 4F
→
06/20 15:40, , 5F
啊 我說的 via suffix tree 是找 common ancestor
06/20 15:40, 5F
→
06/20 15:40, , 6F
你的應該是找 lowest common ancestor 的特例?
06/20 15:40, 6F
推
06/20 16:25, , 7F
反問一個觀念問題,O(n)是constant time?
06/20 16:25, 7F
‣ 更多 hardcover 的文章
文章代碼(AID): #16UCuEtR (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
‣ 更多 hardcover 的文章
文章代碼(AID): #16UCuEtR (Prob_Solve)