问题标签 [lowest-common-ancestor]

命令行上的输入将是这样的：

如您所见，我可以使用 Node 类对其进行硬编码，但我想使用上面提到的命令行输入来构建树。

输入格式：第一个数字是家庭中唯一成员的数量。然后，两个选定的人在一个家庭中，即；D、F，然后其余行包含两个人的姓名，并带有空格分隔符。AB 表示，A 比 B 高级，B 比 E 和 D 高级等。为简单起见，第一个集合是 AB，必须将 A 视为树的根。

那么，我如何通过命令行读取输入并构建与我能够通过 , 等执行的相同的root = Node('A')树root.left = Node('B')？

我正在尝试学习 LCA，因此非常感谢以最简单的方式在正确方向上提供一些帮助。

我有一个问题，这里显示。有人可以建议解决这个问题的方法吗？我查阅了社论，它说我们应该为每个范围创建一个树并将其视为一个节点。我无法理解这个概念和树转换的过程。提前感谢您的帮助！问题的详细信息：

如果一个序列具有以下形式，则称为正确的括号序列：

• 空序列被认为是正确的括号序列。

• (A) 被认为是正确的括号序列。

• 如果 X 和 Y 都是正确的括号序列，则 XY 被认为是正确的括号序列。

一个序列只有在形式 (A) 上才称为强括号序列，其中 A 是正确的括号序列。

您必须计算一个奇怪的和：每两个 A 子数组取 [i1, j1] 和 [i2, j2]。子数组不能相交（即 i1 ≤ i2 和 j1 ≤ i2）并且必须是强括号序列。然后，我们将子数组的最小长度加到总和上，例如它也是一个强括号序列，它同时包含 [i1, j1] 和 [i2, j2]（即如果最小长度的子序列是 [i3, j3]，则 [i3, j3] 是一个强括号序列，并且 i3 ≤ i1 ≤ j1 ≤ j3 和 i3 ≤ i2 ≤ j2 ≤ j3)。

PS我无法理解范围树转换的概念以及LCA如何在这种情况下提供帮助。谢谢。

Using NetworkX

I want to get lowest common ancestor from node1 and node11 in DiGraph.

The following is the code.

I have a problem with a execution speed, so I want faster execution speed.

If you have any good idea or algorithm, please tell me the idea.

Sorry for the poor English.

我想从节点“a”和节点“o”获取所有 LCA 节点。

在这个有向图中，节点“l”和节点“m”是 LCA 节点。

以下是代码。

我想要更快的执行速度。

如果您有比前面提到的更好的方法来解决问题，请告诉我。

我会很感激你的帮助。

I encountered the following implementation and spent some time, but still can't grasp the idea. Could someone please explain line by line what it is doing? I just don't understand at what point it can decide a node is an ancestor.

Thank you

我有一棵树。我想回答以下问题：

1. 在路径上添加值
2. 在路径上获取总和

我正在使用重光分解。n树中有节点和m查询。使用 HLD，当我知道Lowest Common Ancestor时，我可以将任何查询u和v分成两个不同的查询： from utolca和 from vto lca。因此，查询将得到及时回答O(log^2n)（log从u和v到lca，以及log重路径上的分段树）。

如您所知，HLD 是按O(n)时间构建的，因此总时间为O(n + m*log^2n). 我的问题是如何使用已经构建的 HLD 找到 LCA。我无法发明算法。

我可以使用二进制爬升来获得 LCA，但它需要O(nlogn)预处理，这会使渐近行为变得更糟。我也可以使用Range Minimum Query，这不会浪费时间，但我想在这个过程中使用 HLD。谢谢你的任何想法！

这是我提出的用于非递归查找二叉树中两个节点的最低共同祖先的算法。以下是基本策略：

1. 使用字典/哈希表来存储树。每个键值对代表一个节点及其父节点。
2. 从两个节点中的每一个开始，通过将表示每个节点的值的变量设置为其父节点的值，将遍历的值存储在一个哈希集中（两个节点中的每一个节点一个），从而向上遍历树。
3. 当满足以下任一条件时，搜索完成： (a) 两个节点的值相等；或 (b) 当两条路径相互交叉时（即节点 1 的遍历值的哈希集包含节点 2 的当前值，反之亦然）；或 (c) 传入的节点在树中不存在（在这种情况下，算法终止并返回 -1）。

我的理解是，我的算法的最坏情况时间和空间复杂度是 O(log(n))，因为我们永远不需要进行超过 2 * 高度遍历或在哈希集中存储超过 2 * 高度值（并且因为哈希集和树字典的查找时间为 O(1))。

以下是我的代码（C#）。请告知我的分析是否正确，或者是否有更有效（非递归）的方法来执行此操作：

我的问题的答案可能很明显，而且我在纸上知道这个明显的答案。我的意思是，当涉及到一些示例时，我理解为什么我们不允许使用循环来运行最低公共祖先算法，但是我在理解为解决 DAG 中的 LCA 而编写的论文时遇到了问题。所以解决方案的哪一部分阻止我们在循环图上使用它..

我愿意知道并且很感激被告知：

• 您能解释一下 DAG 中 LCA 问题的一种解决方案，而无需太多公式吗？
• 你能确定哪个步骤有循环问题吗？为什么？

在我的问题中，找到它们的 LCA 的节点对不在一个循环内，所以我认为可能有一种方法可以解决这个问题。

提前致谢

我正在寻找一种方法来找到嵌套集中的最低共同祖先可以使用单个方程找到。

例如，来自以下图片：https ://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg

西装和女士之间的 LCA 是服装。我可以使用基于级别的系统来确定父级会面的位置，但这种情况的用例是在数据库设计中，因此提高级别将不利于性能。

我希望我可以使用西装 (3:8) 和女士 (10:21) 的单一计算来得出服装的组合 (1:22)，也就是说，如果存在这样的等式。

如何在不使用递归的情况下找到二叉树的最低共同祖先？