作者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