e******s
发帖数: 38 | 1 题目是find lowest common ancestor in a binary tree (不是BST)。请问
（1）是不是一个node不能是本身的ancestor？ 比如如果p是q的parent, 则lowest common
ancestor是p的parent (而不是p)?
（2）以下的code是career cup 上找到的，是不是没有考虑初始的时候 root == p ||
root ==q的情况？
请大牛讲讲，能给个标准的code就更感谢了！
Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
if(root == NULL)
return NULL;
if (p == NULL || q == NULL)
return NULL;
if(root->leftChild == p || root->leftChild == q || root->rightChild == p||
root->rightChild == q)
return root;
Node * L = LowestCommonAncestor(root->leftChild, p, q);
Node * R = LowestCommonAncestor(root->rightChild, p, q);
if(L != NULL && R != NULL)
return root;
else if (L != NULL)
return L;
else
return R;
} | s*****y
发帖数: 897 | 2 This code is for BST right?
common
|
【在 e******s 的大作中提到】
: 题目是find lowest common ancestor in a binary tree (不是BST)。请问
: （1）是不是一个node不能是本身的ancestor？ 比如如果p是q的parent, 则lowest common
: ancestor是p的parent (而不是p)?
: （2）以下的code是career cup 上找到的，是不是没有考虑初始的时候 root == p ||
: root ==q的情况？
: 请大牛讲讲，能给个标准的code就更感谢了！
: Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
: if(root == NULL)
: return NULL;
: if (p == NULL || q == NULL)
| d**e
发帖数: 6098 | 3 好像是缺了查root==p || root==q的情况
common
|
【在 e******s 的大作中提到】
: 题目是find lowest common ancestor in a binary tree (不是BST)。请问
: （1）是不是一个node不能是本身的ancestor？ 比如如果p是q的parent, 则lowest common
: ancestor是p的parent (而不是p)?
: （2）以下的code是career cup 上找到的，是不是没有考虑初始的时候 root == p ||
: root ==q的情况？
: 请大牛讲讲，能给个标准的code就更感谢了！
: Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
: if(root == NULL)
: return NULL;
: if (p == NULL || q == NULL)
| P**l
发帖数: 3722 | 4 不是吧
【在 s*****y 的大作中提到】
: This code is for BST right?
:
: common
: |
| s*****y
发帖数: 897 | 5 24.3 Design an algorithm and write code to find the first common ancestor of
two
nodes in a binary search tree. Avoid storing additional nodes in a data
structure.
【在 P**l 的大作中提到】
: 不是吧
| b*******8
发帖数: 37364 | 6 问题1其实不是问题，就是个理解问题，树上差了一级而已。面试碰到这种不清楚的，
直接问他澄清就是了。
（1）是不是一个node不能是本身的ancestor？ 比如如果p是q的parent, 则lowest
common ancestor是p的parent (而不是p)? | P**l
发帖数: 3722 | 7 code里哪里用到比大小了？
of
【在 s*****y 的大作中提到】
: 24.3 Design an algorithm and write code to find the first common ancestor of
: two
: nodes in a binary search tree. Avoid storing additional nodes in a data
: structure.
| e******s
发帖数: 38 | 8 这个题不是BST， 就是一般的binary tree.
当然有别的题是BST里找。
of
【在 s*****y 的大作中提到】
: 24.3 Design an algorithm and write code to find the first common ancestor of
: two
: nodes in a binary search tree. Avoid storing additional nodes in a data
: structure.
| e******s
发帖数: 38 | 9 改了一下code, 请大家看看有什么问题没？
assume: 如果p是q的 parent/ancestor， 则他们的lowest common ancestor是p的
parent
// lowest common ancestor in a binary tree
Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
if(!root)
return NULL;
if (!p|| !q)
return NULL;
if(root==p || root==q)
return NULL;
if(root->leftChild == p || root->leftChild == q || root->rightChild == p||
root->rightChild == q)
return root;
Node * L = LowestCommonAncestor(root->leftChild, p, q);
Node * R = LowestCommonAncestor(root->rightChild, p, q);
if(L != NULL && R != NULL)
return root;
else if (L != NULL)
return L;
else
return R;
}
【在 d**e 的大作中提到】
: 好像是缺了查root==p || root==q的情况
:
: common
: |
| i**********e
发帖数: 1145 | 10 1) 一个 node 可以是 ancestor。例如，如果 p 是 q 的 parent， 那 LCA 就是 p 本
身。
2）解这题之前要问清楚面试官是否存在 parent 指针。如果存在的话比较简单，不用
递归解决。至于不存在 parent 指针的话，可以利用递归来解，要考虑的情况比较多。
common
|
【在 e******s 的大作中提到】
: 题目是find lowest common ancestor in a binary tree (不是BST)。请问
: （1）是不是一个node不能是本身的ancestor？ 比如如果p是q的parent, 则lowest common
: ancestor是p的parent (而不是p)?
: （2）以下的code是career cup 上找到的，是不是没有考虑初始的时候 root == p ||
: root ==q的情况？
: 请大牛讲讲，能给个标准的code就更感谢了！
: Node *LowestCommonAncestor(Node *root, Node* p, Node * q) {
: if(root == NULL)
: return NULL;
: if (p == NULL || q == NULL)
| | | i**********e
发帖数: 1145 | 11 Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
// this assumes p and q both exists in the binary tree
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; // one of p or q is on one side
}
By the way, there is an optimization we could make in the above code. That is, what if we already found p and q in the left side of one subtree? Then as we recursively traverse back to the root, we DO NOT need to find if p and q exists in the right subtree (which for sure doesn't exist). | d*******l
发帖数: 338 | 12 这个方法不错。以前还真没想过没有parent该怎么弄，这个看起来更简洁
【在 i**********e 的大作中提到】
: Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
: // this assumes p and q both exists in the binary tree
: 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; // one of p or q is on one side
: }
| s**x
发帖数: 7506 | 13
A
B. C
DE. F G
This code is not right. Think the tree above, for A D, lca is A, you will
return C.
【在 i**********e 的大作中提到】
: Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
: // this assumes p and q both exists in the binary tree
: 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; // one of p or q is on one side
: }
| s**x
发帖数: 7506 | 14
A
B. C
DE. F G
This code is not right. Think the tree above, for A D, lca is A, you will
return C.
【在 i**********e 的大作中提到】
: Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
: // this assumes p and q both exists in the binary tree
: 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; // one of p or q is on one side
: }
| i**********e
发帖数: 1145 | | e******s
发帖数: 38 | 16
Thanks a lot.
【在 i**********e 的大作中提到】
: Assume the definition is when p is ancestor of q, then LCA of (p,q) = p.
: // this assumes p and q both exists in the binary tree
: 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; // one of p or q is on one side
: }
| p*****u
发帖数: 310 | 17 Can you give a optimized solution? The optimized code looks not clean to me
. |
|
