问题标签 [lowest-common-ancestor]

想象一个如下的有向无环图，其中：

• “A”是根（总是只有一个根）
• 每个节点都知道它的父节点
• 节点名称是任意的 - 无法从中推断出任何内容
• 我们从另一个来源知道节点按 A 到 G 的顺序添加到树中（例如，它们是版本控制系统中的提交）

我可以使用什么算法来确定两个任意节点的最低共同祖先 (LCA)，例如，以下的共同祖先：

• B和E是B
• D和F是B

笔记：

• 从根到给定节点不一定只有一条路径（例如“G”有两条路径），因此您不能简单地遍历从根到两个节点的路径并寻找最后一个相等的元素
• 我找到了树的 LCA 算法，尤其是二叉树，但它们不适用于这里，因为一个节点可以有多个父节点（即这不是一棵树）

假设我有四个类：A、B派生自A、C派生自A和D派生自C。（所以我总是有单一继承。）在python中，确定任何两个（此类实例）类的最近共同祖先的最佳方法是什么？具体来说，我需要一个函数clcoancl(X,Y)，其中clcoancl(A, B) == A、clcoancl(B, C) == A和clcoancl(C, D) == C。

给定：X -> B -> C -> D -> Child我希望 jQuery 将所有祖先返回到匹配某个选择器的第一个节点。

jQuery$(Child).parents(X)将只返回X而不是X, B, C, D. 我知道我可以用来parent()手动构建这个数组，但是有更好的方法吗？

首先，我知道还有很多其他线程在处理这个问题。我想知道的是为什么当我在 CodeEval 上提交解决方案时，它的排名似乎没有达到 100%。它仅占70％。当我在本地环境中对其进行测试时，它适用于我遇到的所有测试情况。

我知道我的解决方案不是最有效的。我试图做的是自己想出一个我能理解的解决方案。我最终会将它与其他人进行比较。但在此之前，有人可以解释一下我在这里做错了什么吗？

我正在尝试为无根树实现 LCA。我给出了一棵树（一个无环的连通无向图）和一系列关于 LCA 的查询，用于一些根和两个顶点。每个特定的查询都可以有不同的根，所以我不能使用在一开始就为任意根预处理树的算法。

到目前为止，我已经尝试使用 DFS 找到从两个顶点到根的路径，然后检查它在哪里发散，但它有点慢（O（nq），其中 q 是查询数）。

有什么建议如何预处理树以获得查询的次线性复杂性？

我试图了解破解编码面试第 129 页中的解决方案之一。这是关于找到最低的共同祖先。请看下面的代码。我的问题在评论中

总之，我的问题是：

1）对于这行代码：

为什么返回 root.left 而不是 root？

2）对于这些代码行：

如果root==p，为什么要返回p，这怎么是祖先？同样对于 q。

下面是整个代码：

我的问题是找到一个通用树的 LCA，该树将从 txt 文件中的列表创建。我正在寻找最有效的实施。数据形式为：Id、info、ParentId

数据不以任何方式排序。我正在考虑创建一棵树，但这至少需要 O (nlogn)。虽然日志基数不是 2。这取决于我想的孩子的平均数量。

相反，如果我将节点存储在哈希表中，那么找到 LCA 会比 O (nlogn) 更好。正确的？对于目标节点的每个父节点，我必须检查它是否已被源节点访问（假设我们从源节点开始到根节点并将途中的所有父节点标记为已访问），这需要 O （登录）。因为，我们只检查父母，它会比 O(nlogn) 更好。

有更好的主意吗？

假设我们有这个简单的本体作为玩具示例：

我现在收到关于某个对象 x 的证据（例如，“x 是船”、“x 是汽车”），并想就我对这个对象的了解发表声明。

一个明智的方法是使用我的树并计算我的证据的最低共同祖先（LCA），并将其作为结果返回。在我的示例（汽车和船）中，这将导致车辆。

现在假设我有证据表明对象 y 是car和vehicle。这些的 LCA 是车辆。但是，在这种情况下，我希望结果是car，因为 y 是车辆的证据并不与它是car相矛盾。

我实现了这种替代 LCA 算法（通过忽略其他证据的根路径上的证据），但在互联网上没有找到任何关于这种方法的信息。我使用的替代算法有名称吗？

我很容易实现和理解按顺序和后序遍历的 LCA。

但是，有一种递归的自下而上的方法。

网上看了下代码，有一行没看懂：

这是代码：

val1 和 val2 是需要找到 LCA 的两个节点的值。

最后一行是我坚持的地方。

有人可以解释一下吗？

谢谢你。

我知道这个问题已经被问过很多次了。我需要对二叉树（不是 BST）的 LCA 进行一些澄清。如果我试图从给定的树中找到两个节点（3,11）的 LCA：

代码为 (3,11) 返回 11。

在这里我很困惑，应该是4对。如果我错了，请纠正我。我在这里感到困惑吗？还是 LCA 是如何工作的？