作者hardcover (精装版喔)
看板Prob_Solve
标题Re: [问题] ancestry problem
时间Wed Jun 20 17:23:39 2007
※ 引述《hardcover (精装版喔)》之铭言：
: 标题: [问题] 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
: → hardcover:想到一个，traversal时要对node encoding，不知是不是 06/20 15:03
: → hardcover:正解 06/20 15:04
: 推 ledia:via suffix tree ? 06/20 15:39
: → ledia:encoding 是否也是 logn 的一种? 06/20 15:39
对厚 ， 是 logn XD
: → ledia:啊 我说的 via suffix tree 是找 common ancestor 06/20 15:40
: → ledia:你的应该是找 lowest common ancestor 的特例? 06/20 15:40
: 推 ephesians:反问一个观念问题,O(n)是constant time? 06/20 16:25
是我没说清 楚 ，
O(n) 是指第一次，此後问你类似的问是你都要在 O(1) 之内回答。
thanks
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.88.92