c***d
发帖数: 996 | 1 ☆─────────────────────────────────────☆
Pront (阿呆) 于 (Fri Nov 3 17:45:08 2006) 提到:
JOBHUNTING看来的，感觉 O(N)不太够啊。如果是任意两点，要预先保存两点关系的话
，似乎需要 O(N Lg N)：
15. find out whether 2 tree nodes are related (i.e. ancestor-descendant)
requirement: solve it in O(1) time, with O(N) space (there are N nodes in
the tree), pre-processing is allowed
hint: traverse the tree twice, in normal order and in reverse-order
hint: traverse the tree once is also possible
☆─────────────────────────────────────☆
pxu (Li |
|
