问题标签 [least-common-ancestor]

因此，我阅读了有关 RMQ（范围最小查询）的 TopCoder 教程，我遇到了一个大问题。

在他介绍方法的部分，到目前为止我能理解的是：

（整个方法实际上使用了稀疏表（ST）算法中引入的方法，从 LCA 到 RMQ以及从 RMQ 到 LCA的缩减）

给定一个数组 A[N]，我们需要将其转换为笛卡尔树，从而使 RMQ 问题成为 LCA（最低公共祖先）问题。稍后，我们可以得到数组 A 的简化版本，并使其成为受限 RMQ 问题。

所以它基本上是两个转换。所以第一个 RMQ 到 LCA 部分很简单。通过使用堆栈，我们可以在 O(n) 时间内进行转换，得到一个数组 T[N]，其中 T[i] 是元素 i 的父元素。树就完成了。

但这是我无法理解的。O(n) 方法需要一个数组 where |A[i] - A[i-1]| = 1，并且该数组在本教程的从 LCA 到 RMQ 的缩减部分中进行了介绍。这涉及到这棵树的欧拉之旅。但是，如何通过转换的最终结果来实现呢？我的方法不是线性的，所以在这种方法中应该被认为是不好的，线性方法是什么？

更新：让我感到困惑的一点

树的图片：

Euler Tour 需要知道每个节点的子节点，就像 DFS（深度优先搜索）一样，而 T[n] 只有每个元素的根，而不是子节点。

我正在尝试获取树中两个节点的最小共同祖先。我已经尝试过了，但问题是if one node is the descendant node for other我无法获得 LCA。
我尝试解决它，然后它仅适用于后代节点。不知道如何进行。

这是我的二叉树的实现（这不是 Lca 的代码，只是二叉树的正常实现，只是为了了解我是如何构造二叉树的）

现在我的问题是如果两个节点在右子树和左子树中都相同，如何找到两个节点的最低共同祖先

那么这个的最低共同祖先应该是什么

我在下面的问题中理解了 nick johnson 的答案，但我不明白如何做上述类型的树

如何在任何二叉树中找到两个节点的最低共同祖先？

网上关于“在二叉树中查找最小共同祖先”的许多答案及其补充问题“查找 2 个节点之间的距离”有 4 个问题：

1. 不考虑重复
2. 不考虑输入节点是否无效/不存在/不在树中
3. 使用额外/辅助存储
4. 尽管获得了答案，但不截断遍历。

我对这个示例进行了编码以克服所有障碍。但由于我在这个方向上没有找到“单一”的答案，如果我的代码有一个我遗漏的重大缺点，我将不胜感激。也许没有。额外的眼球赞赏。

我收到了一个关于在二叉树上找到 LCA 的方法的面试问题。我回应我的想法。毕竟面试官说可以用scala fold函数来完成......但我不知道怎么做，有什么想法吗？

我在stackoverflow上查看了很多其他答案，但找不到任何有效的方法，我要么得到根，要么返回node1本身，我不知道如何递归地执行此操作，并尝试了很多次都结束了同样的方法。任何帮助将不胜感激！

这是我的代码：

我对其进行了编辑以制作每个节点的祖先列表，但我不确定如何检查每个节点以查看列表中的元素是否匹配，因为它们通常大小不同。

继承人的新代码：

我有这段代码可以least common Ancestor在nodes. binary tree我认为时间复杂度是O(log n). 但需要专家意见。这段代码在我的输入上运行得相当好，但我不确定我是否已经对它进行了详尽的测试。

这是代码

我有这个代码，它计算给定的Least common Ancestor两个nodes。Binary tree目前，它假设两个节点都存在。我可以编写一个辅助方法来检查节点是否存在，然后调用该LCABT方法。那将需要遍历树两次。我想知道是否有一种方法可以检查和处理当前代码中不存在节点的情况。

我看到一篇谈论 LCA 算法的文章，代码很简单 http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

但我想知道如何计算算法的时间复杂度，有人可以帮我吗？

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

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

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