问题标签 [least-common-ancestor]

我一直在浏览“git merge-base”手册页，但我无法理解多个合并基础是如何发展的。具体来说，我挂断了手册页中的以下插图：

我只是无法理解这种情况是如何造成的。我试图使用测试存储库在分支之间重新创建这种纵横交错的合并情况，但我无法复制它。在所有情况下，我总是以 A 和 B 都指向的 1 个合并提交结束（而不是 A 和 B 指向独立的合并提交，如图所示）。

谁能说明这种情况是如何出现的？这是常见情况还是错误情况？

在一次工作面试中，我被问到以下问题：

给定一个根节点（到一个结构良好的二叉树）和两个其他节点（保证在树中，并且也是不同的），返回两个节点的最低共同祖先。

我不知道任何最不常见的祖先算法，所以我试图当场制作一个。我生成了以下代码：

我尝试了以下测试用例并得到了我期望的答案：

但我的面试官告诉我“有一类树，你的算法会返回 None。” 我不知道那是什么，我把面试搞砸了。我想不出算法会在不ans变成 2 的情况下到达树底部的情况——我错过了什么？

我正在搜索一个非递归算法版本，用于在用 Java 编写的排序二叉树中查找最小共同祖先。我发现的一切都只是递归版本（即使在 stackoverflow 和其他网站上）。

有人可以写或指导我使用非递归版本（使用 while 循环）吗？如果这个版本在时间复杂度方面更有效，还要写吗？

首先，我对 C 或 C++ 并不陌生。但是，我目前正在 Mac Yosemite 上使用 C++。我只是想编写一个递归函数来返回两个节点的共同祖先，它们由它们的键（数据）变量标识。逻辑很简单，遍历树，直到两个节点都在同一个分支中，这些节点发散的节点就是共同的祖先。带着这个想法，我想出了以下代码：

我应该工作，我做过类似的程序。但是，该程序无法编译。我收到编译器错误"control may reach end of non-void function" 这很奇怪，因为我有返回语句。另外，为了避免这个错误，我尝试在最后添加一个 return 语句，它只返回根节点。我很困惑......我应该对 XCode 设置做些什么吗？我的逻辑错了吗？

目前，我正在开发一个程序，其中一个步骤是检查一个叶子 c 是否与二叉树 T 中的另外两个叶子 a 和 b 位于同一子树中。我目前的方法如下：首先，找到T中每对叶子的LCA，并将其存储在字典中。然后，对于树中的每个节点，找到作为其后代的所有叶子，并将其存储在字典中。然后当我需要确定c是否与a和b在同一个子树中时，我找到a和b的LCA，并检查c是否是它的后代。

我需要对许多不同的 a 和 b 对运行此步骤，并在具有多达 600 个叶子的二叉树上执行此操作，那么是否有更快的算法，或者使用更少内存的算法来完成相同的任务？谢谢。

在考虑编写一个函数来实现它之前，我试着想一个算法。h 表示主父节点与给定节点之间的最大距离。它应该在 o(h^2) 中运行，这意味着提出这样的算法应该更容易，但我经常发现自己使用 o(h) 算法。在了解我是否真的在做 ah^2 操作时，我也会感到困惑。我真的可以使用铅。

非二叉树通常如何表示？一个节点可以拥有的子节点数量没有限制的树。最好使用邻接矩阵或邻接列表并假设没有循环，或者做类似于这个问题的事情->

如何实现非二叉树

并跟进问题，当您有一个 n 叉树时（它们的名称是否正确？）在该树中找到两个给定节点/数据值的最小公共祖先的好方法是什么？我能找到的只是处理二叉树的算法，比如这个->

我试图学习 LCA 算法O(nlog n) 预处理和 O(log n) 查询。我在谷歌翻译的帮助下从一个俄罗斯网站阅读它。但它翻译得不好，我很难理解它. 有人可以帮我吗？

这是我从该网站获取的伪代码

我所了解的

• 我知道我们正在遍历图形并存储每个顶点的时间和时间。

• 我明白什么up[i][j]是顶点的2^j祖先。i

• 我明白为什么up[v][0]=p（因为2^0即顶点的第一个祖先v只是它的父亲）

• 我了解上层函数的作用。它决定了哪个顶点出现在A或之前B。

• 我知道上层(a,b)比 lca 更真实A，同样是第二步。

我在伪代码中提到了我不明白的内容。请帮助我并确认我是否理解了所有内容。

PS->对不起我的英语。对此不太满意。

关于最不常见的祖先算法有很多问题，但是这个不同，因为我试图在编译时确定 LCA，而且我的树既不是二叉树也不是搜索树，即使我的简化版本可能看起来像一。

假设您有一堆包含成员 typedef 的结构parent，这是另一个类似的结构：

它们共同构成一棵树，例如

注意：结构之间没有继承关系。

我想做的是创建一个类型特征least_common_ancestor，这样：

最好的方法是什么？

我不关心算法的复杂性，特别是因为树的深度很小，而是我正在寻找最简单的元程序，它会得到正确的答案。

编辑：我需要能够使用 msvc2013 以及其他编译器构建解决方案，因此constexpr首选没有答案。

我想将图表拆分为其组件（如下面的示例 DAG 所示。请注意每个节点的彩色标识符，因为它们代表组件）。在我找到图片中的组件后，我想找到该组件的根和最后一个子组件。以蓝色组件为例，根是E，最后一个子是H。绿色：根B- 最后一个孩子H。

示例图：

E如果您可以在- H, B- E, B- H, A-之间找到连接，I而无需将其拆分为组件。让我知道，因为这是我的最终目标。

关于组件的编译。这实际上是我的最终目标。我只是想将其包括在内，以使您更好地了解我要实现的目标。一旦我找到这些联系，就不可能了。

我发现有帮助但没有回答我的问题的问题：

• 在有向无环图中找到最低共同祖先的算法？

• 找到两个叶节点的最佳共同祖先，其中节点有零个、一个或两个父节点

（这些答案可能就足够了，但我不知道如何实现它）

笔记：

• 请以 C++ 或 C# 发布所有示例代码（如果您要发布示例代码）

• 这是我的第一个问题。如果我做错了什么，请告诉我。

// 大编辑：重做问题，使其更清楚我想要什么。引入组件，因为我可能认为这会更有帮助。