c********s
发帖数: 817 | 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********t
发帖数: 5706 | 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****n
发帖数: 1093 | |
t*********n
发帖数: 89 | |
p*****2
发帖数: 21240 | |
l****o
发帖数: 315 | |
m***k
发帖数: 946 | 7 你的解法是log(n)
如果是O(n)，不需要parent ptr和level，直接遍历一遍tree就可以了
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.
|
c********s
发帖数: 817 | 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*****e
发帖数: 2992 | 9 怎么知道哪个node level高，哪个node level低？还要traverse才能知道？
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.
|
l*****a
发帖数: 14598 | 10 1大还是2大？
【在 f*****e 的大作中提到】
: 怎么知道哪个node level高，哪个node level低？还要traverse才能知道？
:
: node
|
|
|
l*****a
发帖数: 14598 | 11 哪国人给你面的。。
【在 c********s 的大作中提到】
: 一开始也想这样做，用colored DFS。后来interviewer提示说可以有parent ptr和
: level信息。
: http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf
: 不知有没有更好的方法。
|
c********s
发帖数: 817 | 12 not very sure.
【在 l*****a 的大作中提到】
: 哪国人给你面的。。
|
l***i
发帖数: 1309 | 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*******2
发帖数: 292 | 14 楼主做了那code challenge才又的phone吗？
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.
|
c********s
发帖数: 817 | 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********t
发帖数: 5706 | 16 不懂，你是说遍历，并用backtracking的方法存下两个node所在的path (list),
然后在两个list里找最后的共同node吗？
空间复杂度是多少？
【在 c********s 的大作中提到】
: 一开始也想这样做，用colored DFS。后来interviewer提示说可以有parent ptr和
: level信息。
: http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf
: 不知有没有更好的方法。
|
c********t
发帖数: 5706 | 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
|
p*g
发帖数: 141 | 18 同疑惑
不过这样空间肯定是 罗格恩
比如一串010101， 表示从入特开始， 往左往右
【在 c********t 的大作中提到】
: 不懂，你是说遍历，并用backtracking的方法存下两个node所在的path (list),
: 然后在两个list里找最后的共同node吗？
: 空间复杂度是多少？
|
b***m
发帖数: 5987 | 19 有parent和level信息……这题就没难度了。 |
c********s
发帖数: 817 | 20 一开始interview时对runtime和space complexity并没有要求。就是要讲思路。
【在 c********t 的大作中提到】
: 不懂，你是说遍历，并用backtracking的方法存下两个node所在的path (list),
: 然后在两个list里找最后的共同node吗？
: 空间复杂度是多少？
|
