f******6
发帖数: 723 | 1 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
如何找他们的lowest common ancestor。
如果是BST（但这里不是），这是个经典的问题。
你的solution要O(lgn)time和constant space。
如果大家已经讨论过，能不能给我一个link看看？
经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
谢谢大家。 |
r**u
发帖数: 1567 | 2 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不是很好，这样有戏么？
: 谢谢大家。
|
q*********u
发帖数: 280 | 3 我自己胡乱写了一个伪代码，指正一下
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不是很好，这样有戏么？
: 谢谢大家。
|
r****o
发帖数: 1950 | 4 可以用两个数组分别保存到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******6
发帖数: 723 | 5
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.
:
: 戏么？
|
f******6
发帖数: 723 | 6
constant space ...
这个不行
【在 r****o 的大作中提到】
: 可以用两个数组分别保存到p和q的路径，然后比较。
:
: 戏么？
|
r****o
发帖数: 1950 | 7 sorry, 没看到constant space.
【在 f******6 的大作中提到】
:
: constant space ...
: 这个不行
|
f******6
发帖数: 723 | 8
=
呵呵， 如果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));
: }
|
q*********u
发帖数: 280 | 9 那就填两个判断 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。。。
|
r**u
发帖数: 1567 | 10 FT, I thought it's BST...
【在 f******6 的大作中提到】
:
: =
: 呵呵， 如果p在q下面，vice versa。。。这里同时用parent不行吧。
: 不过最后我用的recursion，为了那个constant space。。。
|
|
|
j**l
发帖数: 2911 | 11 实话说，我只知道在有指向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不是很好，这样有戏么？
: 谢谢大家。
|
f******6
发帖数: 723 | 12
我就是想到这个。呵呵，不过题目里n是tree nodes个数，所以，算lgn？
【在 j**l 的大作中提到】
: 实话说，我只知道在有指向parent指针的情况下的O(n)算法，其中n是树的最大高度。
: 先移动p或q使得p，q同层，然后同步向上移。
:
: 戏么？
|
j**l
发帖数: 2911 | 13 你这里的n是树的节点个数还是树的最大高度？
戏么？
【在 f******6 的大作中提到】
: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。
|
j**l
发帖数: 2911 | 14 如果树不平衡，最坏情况下高度就是O(n)
【在 f******6 的大作中提到】
:
: 我就是想到这个。呵呵，不过题目里n是tree nodes个数，所以，算lgn？
|
f******6
发帖数: 723 | 15
对，我也认为是这样。不过interviewer没有质疑O(lgn)。。。应该没有tree is
balanced 这个假设
我现在想想，又想不通了。。。
【在 j**l 的大作中提到】
: 如果树不平衡，最坏情况下高度就是O(n)
|
a***9
发帖数: 364 | 16 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**********i
发帖数: 177 | 17 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***9
发帖数: 364 | 18 这个写的很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********s
发帖数: 133 | 19 这个解法是递归的，空间不是常数吧。需要树高(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***9
发帖数: 364 | 20 这个。。对不是bst的树，根本不知道node value之间的关系，不让用递归stack，就算
循环也是要记录吧.
时间复杂度来说，看起来起码对左右分支的查找是相互独立的，这里大概可以assume可
以并行的做，要不然，没有order的树用什么策略找都有可能要O(n)吧.这段程序我主要
怀疑的是时间复杂度O(logn*logn).
当然，我不清楚,是胡说。
麻烦看一下我的ugly代码..
【在 i********s 的大作中提到】
: 这个解法是递归的，空间不是常数吧。需要树高(logn）的栈。
: 而且时间复杂度也不是log(n)的。一种情况是p,q分别在树根的左右两边，而p需要遍历
: 完左边的所有节点才知道。q需要遍历所有右边节点才知道。
: 所以复杂度至少是遍历所有节点。
|
|
|
k**********i
发帖数: 177 | 21 恩 我好像看错题目了 是bst的解法 可以知道node value之间的关系。。
【在 a***9 的大作中提到】
: 这个。。对不是bst的树，根本不知道node value之间的关系，不让用递归stack，就算
: 循环也是要记录吧.
: 时间复杂度来说，看起来起码对左右分支的查找是相互独立的，这里大概可以assume可
: 以并行的做，要不然，没有order的树用什么策略找都有可能要O(n)吧.这段程序我主要
: 怀疑的是时间复杂度O(logn*logn).
: 当然，我不清楚,是胡说。
: 麻烦看一下我的ugly代码..
|
a***9
发帖数: 364 | 22 不会啊，我觉得你的程序是对的，只不过复杂度我有点疑惑
【在 k**********i 的大作中提到】
: 恩 我好像看错题目了 是bst的解法 可以知道node value之间的关系。。
|
i********s
发帖数: 133 | 23 如果知道父节点指针，用上面提到的方法，是可以在常数空间和logn时间内解决的。
【在 a***9 的大作中提到】
: 这个。。对不是bst的树，根本不知道node value之间的关系，不让用递归stack，就算
: 循环也是要记录吧.
: 时间复杂度来说，看起来起码对左右分支的查找是相互独立的，这里大概可以assume可
: 以并行的做，要不然，没有order的树用什么策略找都有可能要O(n)吧.这段程序我主要
: 怀疑的是时间复杂度O(logn*logn).
: 当然，我不清楚,是胡说。
: 麻烦看一下我的ugly代码..
|
i********s
发帖数: 133 | 24 如果知道父节点指针，用上面提到的方法，是可以在常数空间和logn时间内解决的。
【在 a***9 的大作中提到】
: 这个。。对不是bst的树，根本不知道node value之间的关系，不让用递归stack，就算
: 循环也是要记录吧.
: 时间复杂度来说，看起来起码对左右分支的查找是相互独立的，这里大概可以assume可
: 以并行的做，要不然，没有order的树用什么策略找都有可能要O(n)吧.这段程序我主要
: 怀疑的是时间复杂度O(logn*logn).
: 当然，我不清楚,是胡说。
: 麻烦看一下我的ugly代码..
|
a***9
发帖数: 364 | 25 en, make sense
脑筋急转弯啊 还要猜条件..换作我肯定挂了
【在 i********s 的大作中提到】
: 如果知道父节点指针，用上面提到的方法，是可以在常数空间和logn时间内解决的。
|
c********t
发帖数: 1756 | 26 这题要用等价的 range-min queries 解。 |
k**********i
发帖数: 177 | 27 恩 我发现了 程序没问题 只要是binary tree 就可以的 不一定是bst。。。复杂度我
也没看出
来， 我觉得好像最坏的话 应该是logn*logn了
【在 a***9 的大作中提到】
: 不会啊，我觉得你的程序是对的，只不过复杂度我有点疑惑
|
y**i
发帖数: 1112 | 28 我怎么感觉这个就跟两个链表有公共结点，找公共结点的题目一样啊
首先确定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***l
发帖数: 129 | 29 确定层数需要O(n)吧,如果没有父节点的话
【在 y**i 的大作中提到】
: 我怎么感觉这个就跟两个链表有公共结点，找公共结点的题目一样啊
: 首先确定p和q的层数（对应链表的长度），然后先移动层数多的那个结点向上（父结点
: ）到和另一个结点同样的层数，然后同时向上移动，找相同的结点指针。
: 复杂度O(lgn)。
: 这两个算同一个类型的题目么？
:
: 戏么？
|
f******6
发帖数: 723 | 30
能不能说的清楚点，为什么有了parent pointer，确定level就是
O(lgn）。谢谢
楼上的，思路就是这个，就是要有parent pointer。
【在 s***l 的大作中提到】
: 确定层数需要O(n)吧,如果没有父节点的话
|
|
|
r****o
发帖数: 1950 | 31 是不是他的程序里面默认树里面存在p和q啊。
这道题要不要判断树里面不存在p或q的情况?
【在 a***9 的大作中提到】
: 不会啊，我觉得你的程序是对的，只不过复杂度我有点疑惑
|
f******6
发帖数: 723 | 32
我的意思是说，如果是个极端不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***9
发帖数: 364 | 33 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***l
发帖数: 129 | 34 preprocess的话,RMQ可以保证O(nlgn).
..
【在 f******6 的大作中提到】
:
: 我的意思是说，如果是个极端不balanced binary tree（比如只有一个left node，然
: 后剩余的n-2 nodes全在right tree)，就算有parent pointer，确定level也是O(n）..
: .请指教一下。。。
|
a***9
发帖数: 364 | 35 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**********1
发帖数: 1113 | 36 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***o
发帖数: 19 | 37 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*****e
发帖数: 197 | 38 你为什么不给出答案呢？
我把提示给出来吧：需要计算两个节点的深度差，然后。。。
戏么？
【在 f******6 的大作中提到】
: 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
: 如何找他们的lowest common ancestor。
: 如果是BST（但这里不是），这是个经典的问题。
: 你的solution要O(lgn)time和constant space。
: 如果大家已经讨论过，能不能给我一个link看看？
: 经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
: 谢谢大家。
|
x****r
发帖数: 99 | 39 上面贴的careercup的解法应该不行吧，空间和时间复杂度都远远不符合要求。。这样
的要求，肯定得知道parent pointer, 不然找一个node就要O(n)，怎么可能logN找到
LCA呢。。 |
