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... 阅读全帖 |
|
e******s
发帖数: 38 | 2 改了一下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 = LowestCommonAncesto... 阅读全帖 |
|
T******n
发帖数: 11 | 3 Implement a function that will find the most recent common ancestor of any
two commits from a given commit graph. The commit graph is represented as a
String[] called commits containing all commit IDs in sorted date order (most
recent first) and a String[][] called parents. The parent IDs for the
commit ID at index i can be found at parents[i]. The last item in the
parents array is always null since this represents the parent of the root
commit. For example, the following commit graph:
... 阅读全帖 |
|
G******e
发帖数: 9567 | 4 Evolution theory:
"Humans share a common ancestor with modern African apes, like gorillas
and chimpanzees, 5 to 8 million years ago. Shortly thereafter, the species
diverged into two separate lineages. One of these lineages ultimately
evolved into gorillas and chimps, and the other evolved into early human
ancestors called hominids. "
So, do you think humans share the same ancestors with other species? |
|
g*******y
发帖数: 202 | 5 在缅甸发现化石
Researchers agree that our immediate ancestors, the upright walking apes,
arose in Africa. But the discovery of a new primate that lived about 37
million years ago in the ancient swamplands of Myanmar bolsters the idea
that the deep primate family tree that gave rise to humans is rooted in Asia
. If true, the discovery suggests that the ancestors of all monkeys, apes,
and humans—known as the anthropoids—arose in Asia and made the arduous
journey to the island continent of Africa almost 4... 阅读全帖 |
|
y*c
发帖数: 904 | 6
The best way I can think of is to traverse the tree but use a stack or
vector to maintain the ancestors of current node during the traversal. Then
copy the ancestor vector/stack when the node is input node1 or node2. Then
search the LCA. |
|
l*****a
发帖数: 559 | 7 问一句有没有parent pointer撒。
wiki上写的是O（h)。
In a tree data structure where each node points to its parent, the lowest
common ancestor can be easily determined by finding the first intersection
of the paths from v and w to the root. In general, the computational time
required for this algorithm is O(h) where h is the height of the tree (
length of longest path from a leaf to the root). However, there exist
several algorithms for processing trees so that lowest common ancestors may
be found more quickly,... 阅读全帖 |
|
b*******8
发帖数: 37364 | 8 问题1其实不是问题，就是个理解问题，树上差了一级而已。面试碰到这种不清楚的，
直接问他澄清就是了。
（1）是不是一个node不能是本身的ancestor？ 比如如果p是q的parent, 则lowest
common ancestor是p的parent (而不是p)? |
|
h**o
发帖数: 548 | 9 请教正确答案。
网上答案是下面这样的，但如果有个child不存在哪？难道返回另一个child?
网上还有种方法用inorder找candidate, 再用preorder找最先出现的candidate，那如
果一个child不存在， 不就找到root了吗？
Node* find_lowest_common_ancestor_BT(Node* root, Node* child1, Node* child2){
if (!root) return NULL;
Node* left=NULL;
Node* right= NULL;
//if either child1 or 2 are root than root is LCA
//and since this algorithm goes from top to down, in the case of one
child is
//ancestor of the other child, the ancestor child will be hit and return.
int... 阅读全帖 |
|
l**********t
发帖数: 5754 | 10
not necessary. Since I don't consider "evolution theory" as a proven fact,
you have to specify exactly what you meant by "sharing common ancestor" ,
and based on what criteria & evidence to say A is B's ancestor. Apparently there is
little controversial if both A & B belong to the same spices. |
|
r****o
发帖数: 1950 | 11 是不是目前面试的关于lowest common ancestor(LCA)的题目都是针对binary search
tree的两个node的LCA啊？
有没有哪道面试题让求binary tree或更general tree的LCA？这样的题目怎么做? |
|
w**t
发帖数: 23 | 12 小弟在看careercup，其中有一题是求二叉树两个节点的Lowest Common Ancestor。
书中先给出一种解法：
1 public Tree commonAncestor(Tree root, Tree p, Tree q) {
2 if (covers(root.left, p) && covers(root.left, q))
3 return commonAncestor(root.left, p, q);
4 if (covers(root.right, p) && covers(root.right, q))
5 return commonAncestor(root.right, p, q);
6 return root;
7 }
8 private boolean covers(Tree root, Tree p) { /* is p a child of root?
*/
9 if (root == null) return false;
10 if (root == p) return true;
11 return covers(root.left, p... 阅读全帖 |
|
j*****u
发帖数: 1133 | 13 粗看了一下，上面的解法应该不是O(n)的
O(n)解法可以这样，DFS的时候得到p和q的从root到它们的path，这个是O(n)的
然后把其中一个path放进hash set里，另外一个path找到第一个set里存在的node就是
lowest common ancestor，这一步是O(log n)
所以是O(n)的 |
|
C***y
发帖数: 2546 | 14 If it's assumed that a node is also the ancestor of itself(according to the
definition), then it's correct. However, the situations that only one or no
provided node exists in the tree need further consideration. |
|
j**y
发帖数: 462 | 15 Find the common ancestor of two nodes in a tree. The tree is not a binary
tree strictly in that the left node is less than the right node. Also this
solution should work for trees with three or four children. Provide both a
recursive and iterative solution. |
|
s*****y
发帖数: 897 | 16 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. |
|
i**********e
发帖数: 1145 | 17 1) 一个 node 可以是 ancestor。例如，如果 p 是 q 的 parent， 那 LCA 就是 p 本
身。
2）解这题之前要问清楚面试官是否存在 parent 指针。如果存在的话比较简单，不用
递归解决。至于不存在 parent 指针的话，可以利用递归来解，要考虑的情况比较多。
common
| |
|
i**********e
发帖数: 1145 | 18 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 ... 阅读全帖 |
|
a**********2
发帖数: 340 | 19 正在学习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 || ro... 阅读全帖 |
|
q****x
发帖数: 7404 | 20 p is p's ancestor or not. |
|
|
n*******w
发帖数: 687 | 22 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
树可以递归定义，很多树的相关概念也递归定义比较好。 |
|
m**********e
发帖数: 22 | 23 我今天试了一下如何写一个Lowest Common Ancestor of a Binary Tree Part I 非递
归的code。怎么也写不好。请教这里的大虾可以好的解法？ |
|
|
w*********2
发帖数: 3 | 25 题目描述：http://www.lintcode.com/en/problem/lowest-common-ancestor/
我用的是top-down策略，即从root向下扫描，如果两个目标点都在左侧或者右侧，则
root移到左节点或者右节点，继续扫描，直到两个目标节点不在同一侧。
小弟不才，在Lintcode上面提交代码始终无法通过，总是在第八个test时fail。实在想
不出来代码问题在哪儿，跪求版上的大牛们指点！附上代码如下：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
if (A == null) {
return B;
} else if (B == null) {
return A;
}
TreeNode node = root;
while (find(node.left, A) && find(node.left, B)) {
node = node.left;
... 阅读全帖 |
|
|
s*******5
发帖数: 126 | 27 和LOWEST COMMON ANCESTOR OF A BINARY TREE要求一样，但给的node是这样的
class Node{
value
parent
}
然后也只给了node1, node2,没有root，这个要怎么做啊，谢谢 |
|
|
h***o
发帖数: 5030 | 29 【 以下文字转载自 Biology 讨论区 】
发信人: howto (天顶星科技), 信区: Biology
标 题: 外行请教most recent common ancestor
发信站: BBS 未名空间站 (Tue Mar 6 22:28:42 2012, 美东)
wikipage
http://en.wikipedia.org/wiki/Most_recent_common_ancestor
说估算人类最近的共同祖先的年代
据说均值是1415 BC
靠谱么
我的直觉是不靠谱
我的想法是这样
第一我没看论文，不知道他们怎么模拟的
据说是考虑了人类真正的迁徙路线
但我还是觉得地理大发现才真正把各大洲连在一起
最近五百年的事情
除非你把赌注都压在南太平洋上那条充满传奇色彩的航线
或者相信亲王的《殷商舰队玛雅征服记》
否则，我觉得这个祖先要么就是存在在最近五百年前后一点
要么就得是冰河时代了吧
第二据说模拟的结果在2000到4000年以前
也就是公元元年到2000BC
没看到分布之前
均值有意义么？ |
|
h***o
发帖数: 5030 | 30 【 以下文字转载自 Biology 讨论区 】
发信人: howto (天顶星科技), 信区: Biology
标 题: 外行请教most recent common ancestor
发信站: BBS 未名空间站 (Tue Mar 6 22:28:42 2012, 美东)
wikipage
http://en.wikipedia.org/wiki/Most_recent_common_ancestor
说估算人类最近的共同祖先的年代
据说均值是1415 BC
靠谱么
我的直觉是不靠谱
我的想法是这样
第一我没看论文，不知道他们怎么模拟的
据说是考虑了人类真正的迁徙路线
但我还是觉得地理大发现才真正把各大洲连在一起
最近五百年的事情
除非你把赌注都压在南太平洋上那条充满传奇色彩的航线
或者相信亲王的《殷商舰队玛雅征服记》
否则，我觉得这个祖先要么就是存在在最近五百年前后一点
要么就得是冰河时代了吧
第二据说模拟的结果在2000到4000年以前
也就是公元元年到2000BC
没看到分布之前
均值有意义么？ |
|
n*****x
发帖数: 686 | 31 写了一下。不用build tree，找ancestor，求p和q到ancestor的距离即可，只是corner
case实在多，发现bug记得告诉我一声
int BST_distance(vector& nums, int p, int q){
if (p>q) return BST_distance(nums,q,p);
int ancestor=-1, grandpa=-1;
bool left;
for (int i=0; i
if (nums[i]>=p && nums[i]<=q){
ancestor=i;
for (int j=i-1, dist=INT_MAX; j>=0; j--){
if (abs(nums[j]-nums[i])
if (nums[j]>nums[i]) left=true;
else... 阅读全帖 |
|
q*d
发帖数: 22178 | 32 ☆─────────────────────────────────────☆
swjtuer (swjtuer) 于 (Tue Mar 30 23:56:30 2010, 美东) 提到:
星期一
早餐 牛奶，煮鸡蛋，玉米馒头，榨菜
早点 芦柑
午餐 中大：绿豆饭，木须肉，海米冬瓜，棒骨菠菜汤
小婴：绿豆饭，三叶瓜炒肉，海米冬瓜，棒骨菠菜汤
午点 冰糖山楂水，蔬菜饼
晚餐 棒骨冬苋菜瘦肉粥，卤肉秋叶夹馍
星期二
早餐 牛奶，蒸鸡蛋，枣泥糕
早点 香蕉
午餐 中大：胡萝卜饭，芹菜炒牛肉，珊瑚豆腐，棒骨凤尾汤
小婴：胡萝卜饭，芹菜炒肉，珊瑚豆腐，棒骨凤尾汤
午点 果汁，卤猪肝
晚餐 豌豆肉末焖饭，番茄虾皮紫菜汤
星期三
早餐 南瓜粥，卤蛋，如意肉卷
早点 脐橙
午餐 中大：金银饭，咸烧白，海米儿菜，棒骨冬苋菜汤
小婴：金银饭，樱桃肉，海米儿菜，棒骨冬苋菜汤
午点 牛奶，蛋卷
晚餐 米饭，蒜苔炒肉，芙蓉蒸蛋，棒骨海带萝卜汤
星期四
早餐 牛奶，蒸鸡蛋，奶香馒头
早点 苹果
午餐 中大：南瓜饭，什锦鱼丸，韭菜炒豆干，番茄菌类鱼汤
... 阅读全帖 |
|
D*********n
发帖数: 279 | 33 http://en.wikipedia.org/wiki/Native_Americans_in_the_United_Sta
Native Americans in the United States
From Wikipedia, the free encyclopedia
Jump to: navigation, search
"American Indian" redirects here. For other indigenous peoples, see
Indigenous peoples of the Americas and other geographic regions. For
Americans from South Asia, see Indian American.
This article may be too long to read and navigate comfortably. Please
consider splitting content into sub-articles and/or condensing it. (January
2... 阅读全帖 |
|
L*********s
发帖数: 3063 | 34 This is the article I wrote yesterday, first posted Chinese.
是啊，中国共产党是一个邪教。
在70多年前，中国处于长期半分裂状态，美英法德俄意日等在中国都有区域代理人。中
华民国中央政府受制于不与国家配合的地方军阀，国家连铁路在地方省份上的口径都无
法统一时，中国孱弱无力。我们作为一个延续了几千年的政治实体，却被西方看作是下
等人，愚昧的低级动物时，是中国共产党，通过内战结束中国的这个状态。
所以，在除台湾外的基本的国家统一下，中共有了它的第一个原罪：中央集权。
在60多年前，除了中国仅承认的西方殖民地香港和澳门，两个不属于中华人民共和国的
城市土地外，中共驱逐了所有的境外资本势力、特工与军队。在1956年。中国共产党迫
使自己的老师，苏联共产党，从中国辽宁省大连市的旅顺特别区撤军的时候，不惜与全
世界两大霸权国家美国和苏联同时交恶，被全世界进行经济封锁，中共才终于结束了作
为列强的傀儡而存在。无论是西方还是苏联。在苏联的长波电台和联合舰队倡议被中共
拒绝后，中苏彻底交恶，紧接着就是中共备受诟病的三年困难时期饿死成百上千万人。... 阅读全帖 |
|
C*I
发帖数: 4736 | 35 相比较而言，石正丽的《Bat origin of human coronaviruses/蝙蝠是人类冠状病毒的
来源》是扎扎实实的抓蝙蝠，解剖蝙蝠，分离病毒，对比DNA,RNA后得出得结论。
请lobbock读一读，说一说，走两步！
http://virologyj.biomedcentral.com/articles/10.1186/s12985-015-0422-1
Review
Open Access
Published: 22 December 2015
Bat origin of human coronaviruses
Ben Hu, Xingyi Ge, Lin-Fa Wang & Zhengli Shi
Virology Journal volume 12, Article number: 221 (2015) Cite this article
Abstract
Bats have been recognized as the natural reservoirs of a large variety of
viruses. Special attention has ... 阅读全帖 |
|
e****i
发帖数: 2152 | 36 【 以下文字转载自 Military 讨论区 】
发信人: erkuai (三天不上bbs,赶得上刘少奇), 信区: Military
标 题: On the Jews and Their Lies, 1543
发信站: BBS 未名空间站 (Wed Jan 12 23:21:23 2011, 美东)
by Martin Luther (1483-1546)
Translated by Martin H. Bertram
copyright © 1971 Fortress Press & Augsburg Fortress - On the Jews and
Their Lies is from Luther’s Works Volume 47. Augsburg Fortress is the
publishing ministry of the Evangelical Lutheran Church in America.
Funded through sales revenue, Augsburg Fortress is called to provide
produ... 阅读全帖 |
|
e****i
发帖数: 2152 | 37 by Martin Luther (1483-1546)
Translated by Martin H. Bertram
copyright © 1971 Fortress Press & Augsburg Fortress - On the Jews and
Their Lies is from Luther’s Works Volume 47. Augsburg Fortress is the
publishing ministry of the Evangelical Lutheran Church in America.
Funded through sales revenue, Augsburg Fortress is called to provide
products and services that communicate the Gospel, enhance faith, and
enrich the life of the Christian community from a Lutheran perspective.
Part I
I had mad... 阅读全帖 |
|
T1
发帖数: 4732 | 38 Andrew Jackson
7th President 1829-37: : He was born in the predominantly Scotch-Irish[
76] Waxhaws area of South Carolina two years after his parents left
Boneybefore, near Carrickfergus in County Antrim. A heritage centre in the
village pays tribute to the legacy of 'Old Hickory', the People's President.
Andrew Jackson then moved to Tennessee, where he served as Governor[77]
James Knox Polk
11th President, 1845-49: His ancestors were among the first Ulster-Scots
settlers, emigrating fro... 阅读全帖 |
|
w*******i
发帖数: 186 | 39 while循环写错了吧，
while (r) {
r = r->getNextSibling();
if (r) return r;
r = r->getParent();
}
如果r没有sibling，那么在循环里第二句r会为NULL，调用r->getParent()会报错
的。
可以改成
TreeNode* ancestor = r->getParent();
while (ancestor && !ancestor.getNextSibling())
ancestor = ancestor.getParent();
if (ancestor)
return ancestor.getNextSibling();
else
return null; |
|
H**********5
发帖数: 2012 | 40 whole code:
package Interview.PhoneInterview.LinkedIn.Tree.BTree.Recurse.
LowestCommonAncestor;
import java.util.HashMap;
import java.util.Map;
class BTreeNodeWithParent{
int val;
BTreeNodeWithParent left;
BTreeNodeWithParent right;
BTreeNodeWithParent parent;
BTreeNodeWithParent(int val){
this.val=val;
this.left=this.right=this.parent=null;
}
}
public class LowestCommonAncestorOfABinaryTreeWithParent {
BTreeNodeWithParent LCA(BTreeNodeWithParent p... 阅读全帖 |
|
J*******g
发帖数: 8775 | 41 http://www.clearbibleanswers.org/questionsanswers/100-how-can-g
How can God PUNISH a person’s family to the 3RD AND 4TH GENERATION?
QUESTION 17
IS IT FAIR FOR GOD TO PUNISH THE INNOCENT? HE SAID, "VISITING THE INIQUITY
OF THE FATHERS UPON THE CHILDREN UNTO THE THIRD AND FOURTH GENERATION OF
THEM THAT HATE ME"! (EXODUS 20:5)
Only four times in Scripture this phrase is recorded. In Exodus
20:5, Exodus 34:7, Numbers 14:18, and Deuteronomy 5:9. These are all in the
writings of Moses. In E... 阅读全帖 |
|
G****e
发帖数: 11198 | 42 The Darker Side Of God
If you ask Christians to describe their quasi-chosen god of worship,
you’ll often hear such descriptors as “wonderful” and “loving.” This
choice of selective designation seems commonplace within the Christian
community. In fact, most churches ignore the Old Testament all together so
that the members feel comfortable propagating this view. Fueled by such
blatant omission, this lengthy chapter will fill the void by offering a look
at the volume of horrendous acts perfo... 阅读全帖 |
|
m****a
发帖数: 9485 | 43 What Is a Chinese Genealogy Like?
Most genealogies include five basic types of information: (1) clan origin; (
2) biographies of ancestors; (3) the pedigree itself; (4) information about
clan tombs, ancestral halls, schools, and so forth; and (5) instructions
from preceding generations to descendants. Usually the pedigree is the main
item, with the other information appearing in a preface. In modern times,
directories of living clan members have frequently been included.
Clan Origin Information.... 阅读全帖 |
|
G****e
发帖数: 11198 | 44 【 以下文字转载自 WaterWorld 讨论区 】
发信人: GoBlue (Wolverines), 信区: WaterWorld
标 题: The Darker Side Of God
发信站: BBS 未名空间站 (Sat Jul 12 13:10:33 2014, 美东)
The Darker Side Of God
If you ask Christians to describe their quasi-chosen god of worship,
you’ll often hear such descriptors as “wonderful” and “loving.” This
choice of selective designation seems commonplace within the Christian
community. In fact, most churches ignore the Old Testament all together so
that the members feel comfortable propagatin... 阅读全帖 |
|
|
J*****3
发帖数: 4298 | 46 笑死我了，还来玩黑白颠倒的吗？
我给你全文吧，这么撒谎的话，是耶稣教的吗？撒谎神不喜悦
这篇文章是基督教手册用来歪曲人类进化不成立的，是JAMES给我了文章的一个LINK，但是文章看不全，我根据作者名字找到了全文，也读了，发现，文章根本没有说进化不成立，他们断章取义，黑白颠倒地撒谎。我BS这种恶心的行为。
“5、大概在97年，一个著名的非基督徒考古学家，在非洲发现的所谓人类化石，把一
直以来公认的人类进化顺序，猿人——直立人——能人——智人，给彻底推翻了。目前
人类进化链条重新归零，变为空白。”
原文
http://news.nationalgeographic.com/news/2010/05/100506-science-
翻译：
“Even if the new result doesn't quite settle the debate about whether
Neandertals mixed with modern humans, it does underscore how different they
were from our own lineage. And t... 阅读全帖 |
|
|
s*******h
发帖数: 3219 | 48 【 以下文字转载自 Seattle 讨论区 】
发信人: flying820 (忍冬), 信区: Seattle
标 题: 田野上的鬼魂？ ——由被消失的早期华州中国移民说起
发信站: BBS 未名空间站 (Fri Nov 1 01:57:19 2013, 美东)
赶写于Halloween之夜 ，写完了才发现时间上太应景了:) 欢迎评论
田野上的鬼魂？
——由被消失的早期华州中国移民说起
明天是西雅图抗议ABC宣扬种族屠杀言论的Jimmy Kimmel Live Show游行的日子（http://www.seattle.gov/specialevents/events.htm）。 刚才我去接念小学一年级的六岁儿子放学回家，他坐在车后忽然冒出一个问题，“妈妈，你知不知道我的ancestors 从那里来的？他们在那里？”我很诧异娃在万圣节这个小朋友的节日没跟我聊要糖果，而是居然提到这么一个问题。想到明天要去参加的游行，我手扶方向盘认真而缓慢的回答道，“多多，你记住你的ancestors 在中国，因为爸爸妈妈都是从中国来的。一个人忘记自己ancestors, 祖先，是没有根的，像没有根的... 阅读全帖 |
|
