文献求助---Sci Signal - 未名空间MITBBS历史存档

f*62011-09-03 07:09

1 楼

给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
如何找他们的lowest common ancestor。
如果是BST（但这里不是），这是个经典的问题。
你的solution要O(lgn)time和constant space。
如果大家已经讨论过，能不能给我一个link看看？
经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
谢谢大家。

y*12011-09-03 07:09

2 楼

妈妈代签，收到信说是护照已经寄回来了。到CEAC查询状态是“Your visa case is
currently undergoing necessary administrative processing. This processing
can take several weeks. Please follow any instructions provided by the
Consular Officer at the time of your interview. If further information is
needed, you will be contacted. If your visa application is approved, it will
be processed and mailed/available within two business days. ”
请教大家这是什么意思。到底签过了没有？
谢谢！

k*l2011-09-03 07:09

3 楼

Mitochondrial membrane potential is required for MAVS-mediated antiviral
signaling.
Koshiba T, Yasukawa K, Yanagi Y, Kawabata S.
Source1Department of Biology, Faculty of Sciences, Kyushu University, 6-10-1
Hakozaki, Higashi-ku, Fukuoka 812-8581, Japan. k*****[email protected]
http://www.ncbi.nlm.nih.gov/pubmed/21285412
Email：h*******[email protected]

r*u2011-09-03 07:09

4 楼

when branching through the tree, the first node x, where p starts to go left
, and q starts to go right, is the LCA.

戏么？

【在 f******6 的大作中提到】

: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。

m*v2011-09-03 07:09

5 楼

那你https://ceac.state.gov/ceac/ 查出来的状态是什么？administrative
processing 吗？
那你妈护照拿到了吗？
希望你能上来update最新消息啊

a*l2011-09-03 07:09

6 楼

http://www.sendspace.com/file/b9wyzd
sent

q*u2011-09-03 07:09

7 楼

我自己胡乱写了一个伪代码，指正一下
findCommonParent(p, q){
if(parent(p) == parent(q))
return parent(p);
else if(parent(p) == Root || parent(q) == Root || p == Root || q ==
Root)
return Root;
else
return findCommonParent(parent(p), parent(q));
}

给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
如何找他们的lowest common ancestor。
如果是BST（但这里不是），这是个经典的问题。
你的solution要O(lgn)time和constant space。
如果大家已经讨论过，能不能给我一个link看看？
经过提示完成，中间紧张无比（原谅我比较菜），comm

【在 f******6 的大作中提到】

: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。

y*12011-09-03 07:09

8 楼

护照还没拿到，有了消息再来update

【在 m****v 的大作中提到】

: 那你https://ceac.state.gov/ceac/ 查出来的状态是什么？administrative
: processing 吗？
: 那你妈护照拿到了吗？
: 希望你能上来update最新消息啊

r*o2011-09-03 07:09

9 楼

可以用两个数组分别保存到p和q的路径，然后比较。

戏么？

【在 f******6 的大作中提到】

: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。

f*02011-09-03 07:09

10 楼

和我妈的一样，可能是要面签。我妈的状态一直是这个，然后护照状态已经出来，然后
就收到要求面试的通知单了。如果签证已经签发，状态会是ISSUED。通常护照递送更新
有延误，我们在网上看到护照刚出来，当天银行这里已经可以取了。

is
will

【在 y**1 的大作中提到】

: 妈妈代签，收到信说是护照已经寄回来了。到CEAC查询状态是“Your visa case is
: currently undergoing necessary administrative processing. This processing
: can take several weeks. Please follow any instructions provided by the
: Consular Officer at the time of your interview. If further information is
: needed, you will be contacted. If your visa application is approved, it will
: be processed and mailed/available within two business days. ”
: 请教大家这是什么意思。到底签过了没有？
: 谢谢！

f*62011-09-03 07:09

11 楼

left
能具体说说你的算法么？你怎么判断p goes left and q starts to go right。这个
function是pass nodes p and q as parameters.

【在 r**u 的大作中提到】

: when branching through the tree, the first node x, where p starts to go left
: , and q starts to go right, is the LCA.
:
: 戏么？

m*v2011-09-03 07:09

12 楼

好烦，
我给爸妈搞代签也是这样的状态，
签证是AP，就没有改变过
但是查询护照状态已经在安排运送，
不知道几天能拿到护照

【在 f**********0 的大作中提到】

: 和我妈的一样，可能是要面签。我妈的状态一直是这个，然后护照状态已经出来，然后
: 就收到要求面试的通知单了。如果签证已经签发，状态会是ISSUED。通常护照递送更新
: 有延误，我们在网上看到护照刚出来，当天银行这里已经可以取了。
:
: is
: will

f*62011-09-03 07:09

13 楼

constant space ...
这个不行

【在 r****o 的大作中提到】

: 可以用两个数组分别保存到p和q的路径，然后比较。
:
: 戏么？

y*12011-09-03 07:09

14 楼

妈妈代签，收到信说是护照已经寄回来了。到CEAC查询状态是“Your visa case is
currently undergoing necessary administrative processing. This processing
can take several weeks. Please follow any instructions provided by the
Consular Officer at the time of your interview. If further information is
needed, you will be contacted. If your visa application is approved, it will
be processed and mailed/available within two business days. ”
请教大家这是什么意思。到底签过了没有？
谢谢！
{update} 中信的说我妈的相片不合格，要从新准备相片。都怪我疏忽，我用的上次
她签证的照片。是不是要从新填DS160？

r*o2011-09-03 07:09

15 楼

sorry, 没看到constant space.

【在 f******6 的大作中提到】

:
: constant space ...
: 这个不行

m*v2011-09-03 07:09

16 楼

那你https://ceac.state.gov/ceac/ 查出来的状态是什么？administrative
processing 吗？
那你妈护照拿到了吗？
希望你能上来update最新消息啊

f*62011-09-03 07:09

17 楼

=
呵呵，如果p在q下面，vice versa。。。这里同时用parent不行吧。
不过最后我用的recursion，为了那个constant space。。。

【在 q*********u 的大作中提到】

: 我自己胡乱写了一个伪代码，指正一下
: findCommonParent(p, q){
: if(parent(p) == parent(q))
: return parent(p);
: else if(parent(p) == Root || parent(q) == Root || p == Root || q ==
: Root)
: return Root;
: else
: return findCommonParent(parent(p), parent(q));
: }

y*12011-09-03 07:09

18 楼

护照还没拿到，有了消息再来update

【在 m****v 的大作中提到】

: 那你https://ceac.state.gov/ceac/ 查出来的状态是什么？administrative
: processing 吗？
: 那你妈护照拿到了吗？
: 希望你能上来update最新消息啊

q*u2011-09-03 07:09

19 楼

那就填两个判断　isSubNode(p, q)和isSubNode(q, p)
不过感觉这样是不是if太多了，我不知道你说的标准做法，谁能再贴一下。

=
呵呵，如果p在q下面，vice versa。。。这里同时用parent不行吧。
不过最后我用的recursion，为了那个constant space。。。

【在 f******6 的大作中提到】

:
: =
: 呵呵，如果p在q下面，vice versa。。。这里同时用parent不行吧。
: 不过最后我用的recursion，为了那个constant space。。。

f*02011-09-03 07:09

20 楼

和我妈的一样，可能是要面签。我妈的状态一直是这个，然后护照状态已经出来，然后
就收到要求面试的通知单了。如果签证已经签发，状态会是ISSUED。通常护照递送更新
有延误，我们在网上看到护照刚出来，当天银行这里已经可以取了。

is
will

【在 y**1 的大作中提到】

: 妈妈代签，收到信说是护照已经寄回来了。到CEAC查询状态是“Your visa case is
: currently undergoing necessary administrative processing. This processing
: can take several weeks. Please follow any instructions provided by the
: Consular Officer at the time of your interview. If further information is
: needed, you will be contacted. If your visa application is approved, it will
: be processed and mailed/available within two business days. ”
: 请教大家这是什么意思。到底签过了没有？
: 谢谢！
: {update} 中信的说我妈的相片不合格，要从新准备相片。都怪我疏忽，我用的上次
: 她签证的照片。是不是要从新填DS160？

r*u2011-09-03 07:09

21 楼

FT, I thought it's BST...

【在 f******6 的大作中提到】

:
: =
: 呵呵，如果p在q下面，vice versa。。。这里同时用parent不行吧。
: 不过最后我用的recursion，为了那个constant space。。。

m*v2011-09-03 07:09

22 楼

好烦，
我给爸妈搞代签也是这样的状态，
签证是AP，就没有改变过
但是查询护照状态已经在安排运送，
不知道几天能拿到护照

【在 f**********0 的大作中提到】

: 和我妈的一样，可能是要面签。我妈的状态一直是这个，然后护照状态已经出来，然后
: 就收到要求面试的通知单了。如果签证已经签发，状态会是ISSUED。通常护照递送更新
: 有延误，我们在网上看到护照刚出来，当天银行这里已经可以取了。
:
: is
: will

j*l2011-09-03 07:09

23 楼

实话说，我只知道在有指向parent指针的情况下的O(n)算法，其中n是树的最大高度。
先移动p或q使得p，q同层，然后同步向上移。

戏么？

【在 f******6 的大作中提到】

: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。

w*72011-09-03 07:09

24 楼

你好，求问你最后拿到护照的时候，签证过了吗？
谢谢

【在 m****v 的大作中提到】

: 好烦，
: 我给爸妈搞代签也是这样的状态，
: 签证是AP，就没有改变过
: 但是查询护照状态已经在安排运送，
: 不知道几天能拿到护照

f*62011-09-03 07:09

25 楼

我就是想到这个。呵呵，不过题目里n是tree nodes个数，所以，算lgn？

【在 j**l 的大作中提到】

: 实话说，我只知道在有指向parent指针的情况下的O(n)算法，其中n是树的最大高度。
: 先移动p或q使得p，q同层，然后同步向上移。
:
: 戏么？

j*l2011-09-03 07:09

26 楼

你这里的n是树的节点个数还是树的最大高度？

戏么？

【在 f******6 的大作中提到】

: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。

j*l2011-09-03 07:09

27 楼

如果树不平衡，最坏情况下高度就是O(n)

【在 f******6 的大作中提到】

:
: 我就是想到这个。呵呵，不过题目里n是tree nodes个数，所以，算lgn？

f*62011-09-03 07:09

28 楼

对，我也认为是这样。不过interviewer没有质疑O(lgn)。。。应该没有tree is
balanced 这个假设
我现在想想，又想不通了。。。

【在 j**l 的大作中提到】

: 如果树不平衡，最坏情况下高度就是O(n)

a*92011-09-03 07:09

29 楼

int flag_p = 0, flag_q = 0;
int flag = 1;
int possible = 0;
lca (Node * n) {
if (flag_p && flag_q) return;
possible = 0;
if (!flag_p && !flag_q) possible = 1;
if (p == n) flag_p = 1;
if (q == n) flag_q = 1;
if (!flag_p || !flag_q) {
lca (n->left);
if (!flag_p || !flag_q) lca(n->right);
}
if (possible && flag && flag_p && flag_q) {
cout << "lca is " << n << endl;
flag = 0;
}
}
这样子可以么？

戏么？

【在 f******6 的大作中提到】

: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。

k*i2011-09-03 07:09

30 楼

careercup有这个题目的解法吧。。。就是讨论p q 是不是在同一个子树下，如果是
的话就
继续往下找，知道他们不是在同一个子树下，说明当前的节点就是最low的公共节点
了。
node * common(node * T, node *p, node *q)
{
if (T == null)
return ;
if (covers(T->left, p)&&covers(T->left, q))
return common(T->left, p, q);
if (covers(T->right, p))&&covers(T->right, q))
return common(T->right,p,q);
return T;
}
bool covers(node *T, node * p)
{
if (T== null)
return false;
if (T == p)
return true;
return covers(T->left

【在 f******6 的大作中提到】

: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。

a*92011-09-03 07:09

31 楼

这个写的很elegant，问个问题：common的复杂度是O(logn), 每次调用covers又是O(
logn)
的样子，那整体不是O(logn*logn)吗？请赐教！

【在 k**********i 的大作中提到】

: careercup有这个题目的解法吧。。。就是讨论p q 是不是在同一个子树下，如果是
: 的话就
: 继续往下找，知道他们不是在同一个子树下，说明当前的节点就是最low的公共节点
: 了。
: node * common(node * T, node *p, node *q)
: {
: if (T == null)
: return ;
: if (covers(T->left, p)&&covers(T->left, q))
: return common(T->left, p, q);

i*s2011-09-03 07:09

32 楼

这个解法是递归的，空间不是常数吧。需要树高(logn）的栈。
而且时间复杂度也不是log(n)的。一种情况是p,q分别在树根的左右两边，而p需要遍历
完左边的所有节点才知道。q需要遍历所有右边节点才知道。
所以复杂度至少是遍历所有节点。

【在 k**********i 的大作中提到】

: careercup有这个题目的解法吧。。。就是讨论p q 是不是在同一个子树下，如果是
: 的话就
: 继续往下找，知道他们不是在同一个子树下，说明当前的节点就是最low的公共节点
: 了。
: node * common(node * T, node *p, node *q)
: {
: if (T == null)
: return ;
: if (covers(T->left, p)&&covers(T->left, q))
: return common(T->left, p, q);

a*92011-09-03 07:09

33 楼

这个。。对不是bst的树，根本不知道node value之间的关系，不让用递归stack，就算
循环也是要记录吧.
时间复杂度来说，看起来起码对左右分支的查找是相互独立的，这里大概可以assume可
以并行的做，要不然，没有order的树用什么策略找都有可能要O(n)吧.这段程序我主要
怀疑的是时间复杂度O(logn*logn).
当然，我不清楚,是胡说。
麻烦看一下我的ugly代码..

【在 i********s 的大作中提到】

: 这个解法是递归的，空间不是常数吧。需要树高(logn）的栈。
: 而且时间复杂度也不是log(n)的。一种情况是p,q分别在树根的左右两边，而p需要遍历
: 完左边的所有节点才知道。q需要遍历所有右边节点才知道。
: 所以复杂度至少是遍历所有节点。

k*i2011-09-03 07:09

34 楼

恩我好像看错题目了是bst的解法可以知道node value之间的关系。。

【在 a***9 的大作中提到】

: 这个。。对不是bst的树，根本不知道node value之间的关系，不让用递归stack，就算
: 循环也是要记录吧.
: 时间复杂度来说，看起来起码对左右分支的查找是相互独立的，这里大概可以assume可
: 以并行的做，要不然，没有order的树用什么策略找都有可能要O(n)吧.这段程序我主要
: 怀疑的是时间复杂度O(logn*logn).
: 当然，我不清楚,是胡说。
: 麻烦看一下我的ugly代码..

a*92011-09-03 07:09

35 楼

不会啊，我觉得你的程序是对的，只不过复杂度我有点疑惑

【在 k**********i 的大作中提到】

: 恩我好像看错题目了是bst的解法可以知道node value之间的关系。。

i*s2011-09-03 07:09

36 楼

如果知道父节点指针，用上面提到的方法，是可以在常数空间和logn时间内解决的。

【在 a***9 的大作中提到】

: 这个。。对不是bst的树，根本不知道node value之间的关系，不让用递归stack，就算
: 循环也是要记录吧.
: 时间复杂度来说，看起来起码对左右分支的查找是相互独立的，这里大概可以assume可
: 以并行的做，要不然，没有order的树用什么策略找都有可能要O(n)吧.这段程序我主要
: 怀疑的是时间复杂度O(logn*logn).
: 当然，我不清楚,是胡说。
: 麻烦看一下我的ugly代码..

i*s2011-09-03 07:09

37 楼

如果知道父节点指针，用上面提到的方法，是可以在常数空间和logn时间内解决的。

【在 a***9 的大作中提到】

: 这个。。对不是bst的树，根本不知道node value之间的关系，不让用递归stack，就算
: 循环也是要记录吧.
: 时间复杂度来说，看起来起码对左右分支的查找是相互独立的，这里大概可以assume可
: 以并行的做，要不然，没有order的树用什么策略找都有可能要O(n)吧.这段程序我主要
: 怀疑的是时间复杂度O(logn*logn).
: 当然，我不清楚,是胡说。
: 麻烦看一下我的ugly代码..

a*92011-09-03 07:09

38 楼

en, make sense
脑筋急转弯啊还要猜条件..换作我肯定挂了

【在 i********s 的大作中提到】

: 如果知道父节点指针，用上面提到的方法，是可以在常数空间和logn时间内解决的。

c*t2011-09-03 07:09

39 楼

这题要用等价的 range-min queries 解。

k*i2011-09-03 07:09

40 楼

恩我发现了程序没问题只要是binary tree 就可以的不一定是bst。。。复杂度我
也没看出
来，我觉得好像最坏的话应该是logn*logn了

【在 a***9 的大作中提到】

: 不会啊，我觉得你的程序是对的，只不过复杂度我有点疑惑

y*i2011-09-03 07:09

41 楼

我怎么感觉这个就跟两个链表有公共结点，找公共结点的题目一样啊
首先确定p和q的层数（对应链表的长度），然后先移动层数多的那个结点向上（父结点
）到和另一个结点同样的层数，然后同时向上移动，找相同的结点指针。
复杂度O(lgn)。
这两个算同一个类型的题目么？

戏么？

【在 f******6 的大作中提到】

: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。

s*l2011-09-03 07:09

42 楼

确定层数需要O(n)吧,如果没有父节点的话

【在 y**i 的大作中提到】

: 我怎么感觉这个就跟两个链表有公共结点，找公共结点的题目一样啊
: 首先确定p和q的层数（对应链表的长度），然后先移动层数多的那个结点向上（父结点
: ）到和另一个结点同样的层数，然后同时向上移动，找相同的结点指针。
: 复杂度O(lgn)。
: 这两个算同一个类型的题目么？
:
: 戏么？

f*62011-09-03 07:09

43 楼

能不能说的清楚点，为什么有了parent pointer，确定level就是
O(lgn）。谢谢
楼上的，思路就是这个，就是要有parent pointer。

【在 s***l 的大作中提到】

: 确定层数需要O(n)吧,如果没有父节点的话

r*o2011-09-03 07:09

44 楼

是不是他的程序里面默认树里面存在p和q啊。
这道题要不要判断树里面不存在p或q的情况?

【在 a***9 的大作中提到】

: 不会啊，我觉得你的程序是对的，只不过复杂度我有点疑惑

f*62011-09-03 07:09

45 楼

我的意思是说，如果是个极端不balanced binary tree（比如只有一个left node，然
后剩余的n-2 nodes全在right tree)，就算有parent pointer，确定level也是O(n）..
.请指教一下。。。

【在 f******6 的大作中提到】

:
: 能不能说的清楚点，为什么有了parent pointer，确定level就是
: O(lgn）。谢谢
: 楼上的，思路就是这个，就是要有parent pointer。

a*92011-09-03 07:09

46 楼

en, I think it's for average case. For trees like what you said,
it's O(n) anyway.

..

【在 f******6 的大作中提到】

:
: 我的意思是说，如果是个极端不balanced binary tree（比如只有一个left node，然
: 后剩余的n-2 nodes全在right tree)，就算有parent pointer，确定level也是O(n）..
: .请指教一下。。。

s*l2011-09-03 07:09

47 楼

preprocess的话,RMQ可以保证O(nlgn).

..

【在 f******6 的大作中提到】

:
: 我的意思是说，如果是个极端不balanced binary tree（比如只有一个left node，然
: 后剩余的n-2 nodes全在right tree)，就算有parent pointer，确定level也是O(n）..
: .请指教一下。。。

a*92011-09-03 07:09

48 楼

In the case we don't have parent pointer, you can handle that situation if you want,
it's a tiny bug he return the root node for this case.
Anyone comment on my code? If I write code like that to recruiter,
will he definitely turn me down?

【在 r****o 的大作中提到】

: 是不是他的程序里面默认树里面存在p和q啊。
: 这道题要不要判断树里面不存在p或q的情况?

g*12011-09-03 07:09

49 楼

If the link does not has the pointer to the parent, how can you get the
parent? You need start from beginning to find the parent...waste a lot of
time. You only need 100 bits store the path and it can handle all possible
binary tree in the real world.

a*o2011-09-03 07:09

50 楼

You can achieve O(n) space and O(lg(N)) time complexity if you have parent
node pointer stored in each node.
This is achieved by first building d 2 linked list to store paths from root
to each node, and then comparing the linked list to find the last common
node in both list.
You can get a better understanding on LCA problem from this TopCoder
tutorial (see link below). It gives two solutions to this problem.
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
The idea

w*e2011-09-03 07:09

51 楼

你为什么不给出答案呢？
我把提示给出来吧：需要计算两个节点的深度差，然后。。。

戏么？

【在 f******6 的大作中提到】

: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。

x*r2011-09-03 07:09

52 楼

上面贴的careercup的解法应该不行吧，空间和时间复杂度都远远不符合要求。。这样
的要求，肯定得知道parent pointer, 不然找一个node就要O(n)，怎么可能logN找到
LCA呢。。