作者hardcover (精裝版喔)
看板Prob_Solve
標題[問題] ancestry problem
時間Wed Jun 20 14:49:49 2007
給一顆 binary tree，
問某個 node 是不是另一個 node 的 ancestor，
要在 constant time 決定。
允許 O(n) 的 preprocessing。
n: # of node
我做了幾次嚐試都失敗，至少要logn，
3 種 traversal，也看不出什麼線索。
thanks
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.235.76
1F：→ hardcover:想到一個，traversal時要對node encoding，不知是不是 06/20 15:03
2F：→ hardcover:正解 06/20 15:04
3F：推 ledia:via suffix tree ? 06/20 15:39
4F：→ ledia:encoding 是否也是 logn 的一種? 06/20 15:39
5F：→ ledia:啊 我說的 via suffix tree 是找 common ancestor 06/20 15:40
6F：→ ledia:你的應該是找 lowest common ancestor 的特例? 06/20 15:40
7F：推 ephesians:反問一個觀念問題,O(n)是constant time? 06/20 16:25