F家电面 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

F家电面

F家电面# JobHunting - 待字闺中

c*s2012-11-13 08:11

1 楼

刚面完
lowest common ancestor in a binary tree.
Node class 可以有parent pointer 和 level 信息。需要提供一个O（n）（runtime）
，O（1）（space）的解法
想了想可以让level高的node先沿parent pointer traverse到与level低的node相同的
level. 然后两个node同时一个一个level沿parent pointer traverse。一旦两个node
变成相同的node，return 那个node as result.

c*t2012-11-13 08:11

2 楼

Thank you for sharing. You have a very good solution. Good luck!

node

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

: 刚面完
: lowest common ancestor in a binary tree.
: Node class 可以有parent pointer 和 level 信息。需要提供一个O（n）（runtime）
: ，O（1）（space）的解法
: 想了想可以让level高的node先沿parent pointer traverse到与level低的node相同的
: level. 然后两个node同时一个一个level沿parent pointer traverse。一旦两个node
: 变成相同的node，return 那个node as result.

h*n2012-11-13 08:11

3 楼

额，基本就是你说的那个方法就行了。

t*n2012-11-13 08:11

4 楼

挺简单的，祝LZ好运

p*22012-11-13 08:11

5 楼

这题比较直观。

l*o2012-11-13 08:11

6 楼

嗯. 解的好!

m*k2012-11-13 08:11

7 楼

你的解法是log(n)
如果是O(n)，不需要parent ptr和level，直接遍历一遍tree就可以了

node

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

c*s2012-11-13 08:11

8 楼

一开始也想这样做，用colored DFS。后来interviewer提示说可以有parent ptr和
level信息。
http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf
不知有没有更好的方法。

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

: 你的解法是log(n)
: 如果是O(n)，不需要parent ptr和level，直接遍历一遍tree就可以了
:
: node

f*e2012-11-13 08:11

9 楼

怎么知道哪个node level高，哪个node level低？还要traverse才能知道？

node

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

l*a2012-11-13 08:11

10 楼

1大还是2大？

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

: 怎么知道哪个node level高，哪个node level低？还要traverse才能知道？
:
: node

l*a2012-11-13 08:11

11 楼

哪国人给你面的。。

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

: 一开始也想这样做，用colored DFS。后来interviewer提示说可以有parent ptr和
: level信息。
: http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf
: 不知有没有更好的方法。

c*s2012-11-13 08:11

12 楼

not very sure.

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

: 哪国人给你面的。。

l*i2012-11-13 08:11

13 楼

this one is similar to the problem:
Given two head pointers, check whether they point to the same singly linked
list, if yes, find the first node the two lists have in common.

t*22012-11-13 08:11

14 楼

楼主做了那code challenge才又的phone吗？

node

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

c*s2012-11-13 08:11

15 楼

Get it. I find that the problem is listed here.
http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
Thanks!

linked

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

: this one is similar to the problem:
: Given two head pointers, check whether they point to the same singly linked
: list, if yes, find the first node the two lists have in common.

c*t2012-11-13 08:11

16 楼

不懂，你是说遍历，并用backtracking的方法存下两个node所在的path (list),
然后在两个list里找最后的共同node吗？
空间复杂度是多少？

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

c*t2012-11-13 08:11

17 楼

这个是BST

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

: Get it. I find that the problem is listed here.
: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-bin
: Thanks!
:
: linked