由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - least common ancestor的疑惑
相关主题
一个老题binary tree找 lowest common ancestor 的code (请教问两道facebook面试题
Lowest Common Ancestor in a binary tree (no parent pointer)插入节点到complete binary tree的末尾
LCA复杂度Twitter电面未通过
问道G题(3)求教Leetcode题目:Lowest Common Ancestor
Lowest common ancestor of two nodes of Binary TreeLCA复杂度是多少
请问如何求binary tree的lowest common ancestorFind LeastCommonAncestor for N-ary Tree
Lowest Common Ancestor of multiple nodes in a binary treefind the k-th maximum node in a binary search tree 有疑问
关于inordertraversal 的iterative wayfb面经,附答案,求大牛指点
相关话题的讨论汇总
话题: root话题: node话题: ancestor话题: return话题: null
进入JobHunting版参与讨论
1 (共1页)
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
8
返回bool, 用输出参数不就解决了?
1 (共1页)
进入JobHunting版参与讨论
相关主题
fb面经,附答案,求大牛指点Lowest common ancestor of two nodes of Binary Tree
recovery BST 不考虑相同值的情况么?请问如何求binary tree的lowest common ancestor
Amazon 打印给定node距离最近的K个nodesLowest Common Ancestor of multiple nodes in a binary tree
刚看了geekforgeek烙印代码果然一坨屎逻辑混乱关于inordertraversal 的iterative way
一个老题binary tree找 lowest common ancestor 的code (请教问两道facebook面试题
Lowest Common Ancestor in a binary tree (no parent pointer)插入节点到complete binary tree的末尾
LCA复杂度Twitter电面未通过
问道G题(3)求教Leetcode题目:Lowest Common Ancestor
相关话题的讨论汇总
话题: root话题: node话题: ancestor话题: return话题: null