☆─────────────────────────────────────☆
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