这里的二叉树可能不一定是二进制搜索树.
结构可以视为 -
struct node {
int data;
struct node *left;
struct node *right;
};
我可以和朋友一起解决的最大解决方案就是这种 -
考虑这个二叉树:
二叉树http://lcm.csa.iisc.ernet.in/dsa/img151.gif
顺序遍历产量 - 8,4,9,2,5,1,6,3,7
后序遍历产量 - 8,9,4,5,2,6,7,3,1
因此,例如,如果我们想要找到节点8和5的共同祖先,那么我们在顺序树遍历中创建8到5之间的所有节点的列表,在这种情况下恰好是[4,9] ,2].然后我们检查此列表中的哪个节点在后序遍历中最后出现,即2.因此,8和5的共同祖先是2.
这个算法的复杂性,我相信是O(n)(O(n)对于顺序/后序遍历,其余的步骤再次是O(n),因为它们只不过是数组中的简单迭代).但这很有可能是错误的.:-)
但这是一个非常粗略的方法,我不确定它是否会因某些情况而崩溃.这个问题还有其他(可能是更优的)解决方案吗？
algorithm complexity-theory binary-tree least-common-ancestor
这是一个受欢迎的访谈问题,我可以在这个主题上找到的唯一一篇文章来自TopCoder.对我来说不幸的是,从面试答案的角度看,它看起来过于复杂.
除了绘制两个节点的路径并推断祖先之外,是否有更简单的方法可以做到这一点？(这是一个很受欢迎的答案,但是面试问题的变化需要一个恒定的空间答案).
所以我一直在研究实现最低共同的祖先算法.我查看了许多不同的算法(主要是Trajan解决方案的变体或RMQ的变体).
我使用的是非二叉树.我的树通常会在查询之间进行更改,因此预处理不一定是值得的.树不应超过50-75个节点.我想知道的是我是否应该使用他们的算法或只是坚持自己的算法.
我的算法
myLCA(node1, node2) {
parentNode := [ ]
while (node1!=NULL) {
parentNode.push(node1)
node1 := node1.parent
}
while (node2!=NULL) {
for i in parentNode.size {
if (parentNode(i) == node2) {
return node2;
}
}
node2 := node2.parent
}
}
以下是我找到第一个共同祖先的算法.但我不知道如何计算它的时间复杂度,任何人都可以帮忙吗？
public Tree commonAncestor(Tree root, Tree p, Tree q) {
if (covers(root.left, p) && covers(root.left, q))
return commonAncestor(root.left, p, q);
if (covers(root.right, p) && covers(root.right, q))
return commonAncestor(root.right, p, q);
return root;
}
private boolean covers(Tree root, Tree p) { /* is p a child of root? */
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}
我在一次采访中向我询问了这个问题:我有一个二叉树,我必须找到共同的祖先(父)给出该树的两个随机节点.我也得到了一个指向根节点的指针.
我的回答是:
分别遍历两个节点的树,直到到达预期的节点.遍历时并行存储元素和链接列表中的下一个地址.然后我们有两个链接列表.因此,尝试比较两个链表,两个链表中的最后一个公共节点是父列表.
我认为这个解决方案是正确的,如果我错了,请纠正我.如果这个解决方案是正确的,我可能知道这是这项任务的唯一更好的解决方案还是有比这更好的解决方案!
在Python中实现最低共同祖先的最简单方法是什么？我有一个树,每个节点都有一个指向其父节点的节点,我希望能够找到给定两个节点的第一个共同祖先.我想出了几个想法,但没有一个特别有吸引力
让每个节点包含其基数列表,并执行连接,找到最长的公共前缀,然后取最后一个元素.不幸的是,我不知道有任何内置的方法来做最长的公共前缀,所以这需要手动循环.
让每个节点包含一组基础并执行集合交集,并获取最大元素.但这需要定义自定义比较运算符,我甚至不确定它是否可行.
我该怎么办？我正在寻找一些有利于简化而不是性能的东西,因此需要复杂处理的解决方案已经完成.
编辑:我发现虽然没有内置方式,但你可以使用zip在一行中做最长的公共前缀,所以它仍然相当简单.
common = [x for x in zip(*baselists) if len(set(x)) == 1][-1]