我和按摩女的故事——(二)初见 (转载)# Love - 情爱幽幽
A*r
1 楼
topcoder上有关于LCA的算法,比较能够接受的有两个:
1)用DP作preporcessing, 用 O(nlogn) time, 然后查询再用O(logn) time
2) 转化为 restricted RMQ problem, 可以达到O(n) time, O(n) space.
(详见http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor)
不过看到了careercup上给出的一个非DP算法,recursive的,貌似算法复杂度也只有O(
n), 但是没有用多余的空间。。虽然topcoder上面的可以查询任意两个node之间的LCA,
但在实际面试题中,我们一般都是会给定两个node,这样看来careercup上的不是更好
吗?!
下面给出careercup上的算法,大家讨论一下看看。
/* Returns NULL, p, q or the nearest common ancestor of p and q, assume p
and q are in the tree
1)用DP作preporcessing, 用 O(nlogn) time, 然后查询再用O(logn) time
2) 转化为 restricted RMQ problem, 可以达到O(n) time, O(n) space.
(详见http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor)
不过看到了careercup上给出的一个非DP算法,recursive的,貌似算法复杂度也只有O(
n), 但是没有用多余的空间。。虽然topcoder上面的可以查询任意两个node之间的LCA,
但在实际面试题中,我们一般都是会给定两个node,这样看来careercup上的不是更好
吗?!
下面给出careercup上的算法,大家讨论一下看看。
/* Returns NULL, p, q or the nearest common ancestor of p and q, assume p
and q are in the tree