A*********r
发帖数: 564 | 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 | h**6
发帖数: 4160 | 2 以前曾经想过一个方法，先序中序后序遍历二叉树。那么在先序的两个结点之前，中序
的两个结点之中，后序的两个结点之后，一定有一个唯一重复的结点，就是其最低公共
父结点。 | D***h
发帖数: 183 | 3 递归栈你不算空间开销了?
topcoder上讨论的RMQ是可以在任意tree上查找LCA的。
O(
LCA,
【在 A*********r 的大作中提到】
: 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
| A*********r
发帖数: 564 | 4 我知道topcoder上的更general, 我只是说对于这个类型的面试题，有没有更容易直观
的算法。。
我指的空间，是一般面试题中说的需要额外保存的数据结构。
【在 D***h 的大作中提到】
: 递归栈你不算空间开销了?
: topcoder上讨论的RMQ是可以在任意tree上查找LCA的。
:
: O(
: LCA,
| A*********r
发帖数: 564 | 5 好像也可行，不过比较每个的path， 最直接的方法估计要O(n*n)的时间吧。。
【在 h**6 的大作中提到】
: 以前曾经想过一个方法，先序中序后序遍历二叉树。那么在先序的两个结点之前，中序
: 的两个结点之中，后序的两个结点之后，一定有一个唯一重复的结点，就是其最低公共
: 父结点。
|
|
