a**********2 发帖数: 340 | 1 正在学习ihas1337code的blog
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in
L&
R subtrees
}
如果p是q的ancestor,这段code就返回p,但是实际上应该返回p的parent吧?如果p是
root,那么应该返回NULL。不知道是不是我理解错了
我觉得应该把if (root == p || root == q) return root;
改为 if(root == p || root == q) return NULL;
if(root->left == p || root->right == p ||root->left == q || root->right ==
q
) return root; |
q****x 发帖数: 7404 | 2 p is p's ancestor or not.
【在 a**********2 的大作中提到】 : 正在学习ihas1337code的blog : Node *LCA(Node *root, Node *p, Node *q) { : if (!root) return NULL; : if (root == p || root == q) return root; : Node *L = LCA(root->left, p, q); : Node *R = LCA(root->right, p, q); : if (L && R) return root; // if p and q are on both sides : return L ? L : R; // either one of p,q is on one side OR p,q is not in : L& : R subtrees
|
a**********2 发帖数: 340 | 3 p应该不是自己的ancestor
【在 q****x 的大作中提到】 : p is p's ancestor or not.
|
n*******w 发帖数: 687 | 4 The lowest common ancestor is defined between two nodes v and w as the
lowest node in T that has both v and w as descendants (where we allow a node
to be a descendant of itself).
from
http://en.wikipedia.org/wiki/Lowest_common_ancestor
树可以递归定义,很多树的相关概念也递归定义比较好。
【在 a**********2 的大作中提到】 : p应该不是自己的ancestor
|
a**********2 发帖数: 340 | 5 哦,多谢
但是还是有问题,如果p或者q其中一个不在这颗树里,应该返回NULL,但是程序还是会
返回另一个node本身
node
【在 n*******w 的大作中提到】 : The lowest common ancestor is defined between two nodes v and w as the : lowest node in T that has both v and w as descendants (where we allow a node : to be a descendant of itself). : from : http://en.wikipedia.org/wiki/Lowest_common_ancestor : 树可以递归定义,很多树的相关概念也递归定义比较好。
|
n*******w 发帖数: 687 | 6 这个是invalid input问题。可以问interviewer需不需要写code。
先写完问题本身的code,有时间考虑这种复杂点的invalid的情况。
无非就是遍历树,看能不能找到p 和 q。O(n)的时间。
【在 a**********2 的大作中提到】 : 哦,多谢 : 但是还是有问题,如果p或者q其中一个不在这颗树里,应该返回NULL,但是程序还是会 : 返回另一个node本身 : : node
|
f*******t 发帖数: 7549 | 7 这段代码不能处理如果只有一个node在树里的情况,不一定能满足面试时的要求,一定
得跟面试官问清楚 |
w****x 发帖数: 2483 | |