问题标签 [least-common-ancestor]

这里的二叉树不一定是二叉搜索树。
该结构可以被视为 -

我可以与朋友一起解决的最大解决方案是这种类型的 -
考虑一下这个二叉树：

中序遍历产生 - 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)，因为它们只不过是数组中的简单迭代）。但很有可能这是错误的。:-)

但这是一种非常粗糙的方法，我不确定它是否会在某些情况下失效。这个问题还有其他（可能更优化）的解决方案吗？

我正在查看这个问题，然后阅读有关Tarjan 的最不常见的祖先算法。我以前从未遇到过 LCA 算法的任何应用。

这样的 LCA 算法常用在哪里？

我知道以前有人问过类似的问题，但我认为我的解决方案要简单得多。特别是与维基百科相比。

请证明我错了！

如果您有一棵树，其节点具有给定的数据结构：

你可以写一个这样的函数：

这段代码非常简单，最坏的情况是 O(n)，平均情况可能是 O(logn)，特别是如果树是平衡的（其中 n 是树中的节点数）。

有时我会遇到这样的面试问题： “查找树中任意 2 个节点的共同父节点”。我注意到他们也在谷歌、亚马逊等公司提出 LCA 问题。

正如维基百科所说，可以通过从给定节点到根的路径相交来找到 LCA，它需要 O(H)，其中 H 是树的高度。此外，还有更高级的算法可以在 O(N) 中处理树并在 O(1) 中回答 LCA 查询。

我想知道面试官究竟想了解关于提出这个 LCA 问题的候选人的哪些信息。路径交叉的第一个算法似乎微不足道。他们是否希望候选人记住预处理算法？他们是否期望候选人能够即时发明这些算法和数据结构？

以下是我找到第一个共同祖先的算法。但是我不知道如何计算它的时间复杂度，有人可以帮忙吗？

目标：

我正在寻找一种算法来找到图的最佳共同祖先，其中图中的节点可以有零个、一个或两个父节点。我不确定“最佳共同祖先”的术语：更好的术语可能是“最低共同祖先”或“最近的共同祖先”等。如果有更好的术语，请提供描述此类的 URL。

该算法可以访问完整的图形数据结构。

给定节点可能有零个、一个或两个父节点。这是关键，因为我在网上看到的算法假定给定节点有零个或一个父节点，但没有两个父节点（请参阅下面的参考资料）。例如，下图中的 m1 节点的父节点为零，因为它是根（图可以有多个根）。d3有两个父母，一个是d2，另一个是b2。

如果节点存在，则节点对双亲都有引用，如果存在，则对所有子节点都有引用，因此向上遍历树和向下遍历树是公平的游戏。节点可以有零个或多个子节点。更改数据结构不是一种选择。

更靠近两个输入节点的节点比更远的节点（即更靠近图的根）更可取。

例如，下面给出的图表显示了一个可能的图表。在这种情况下，算法的输入将是节点 b5 和 d4。节点 b5 和 d4 的最佳共同祖先是 b2。c2 不会是因为 b3 在通向 b5 的血统中。

该算法的可能答案最多只能是一个节点，在两个输入节点没有共同祖先的情况下，空集是一个有效答案。

参考资料

Tarjan 的离线最小共同祖先算法似乎暗示零个或一个父母，所以如果这是解决方案，那么答案应该包括在该算法中如何考虑两个父母的描述。最低共同祖先的维基百科页面似乎也只考虑了节点有零个或一个父节点的数据结构，而不是两个：

在每个节点都指向其父节点的树数据结构中，...

图：

所以我一直在研究实现最低共同祖先算法。我查看了许多不同的算法（主要是 Trajan 解决方案的变体或 RMQ 的变体）。

我正在使用非二叉树。我的树经常会在查询之间发生变化，因此预处理不一定是值得的。树的节点不应超过 50-75 个。我想知道是我应该打扰使用他们的算法还是坚持我自己的算法。

我的算法

How can I find a least common ancestors of multiple nodes in a directed acyclic graph?

I've found quite a few papers on the topic but they all seem to find LCAs in DAG for two nodes.

Are there good algorithms for multiple nodes?

这个问题可能很多人都问过，但是，它有点不同。我们有一棵二叉树。给你两个节点 p & q。我们必须找到最不常见的父母。但是你没有指向根的根节点指针。为您提供了两个内置功能，它们是：

1) BOOL same(node *p, node *q);-> 如果节点相同，则返回 true，否则返回 false。

2) node* parentNode(node *c);-> 返回一个节点，它是当前节点的父节点。

如果节点 c 实际上是根节点，则 parentNode 函数将为您返回一个NULL值。使用这些函数，我们必须找到树的最不常见的父级。

我有一个表表示组织层次结构的传递闭包（即，它是一个具有单个根的树）：

我有另一个表，其中包含每个用户被允许访问的组织：

系统向用户显示与用户可以访问的每个组织相关的支出汇总。我总是可以首先向用户展示公司的视图（即根），向用户展示直接子组织的列表以及他的组织对总数的贡献。在大多数情况下，只有一个孩子，并且用户需要在看到多个孩子之前向下钻取几个级别。我更愿意从第一个显示多个孩子的组织（即 LCA）开始演示。

对于给定的用户，我可以很容易地找到到根目录的路径集，但在找到最不共同的祖先时遇到了麻烦。我正在使用 postgresql 9.1，但更喜欢与数据库无关的解决方案。在最坏的情况下，我可以将 root 的路径拉回到应用程序的代码中并在那里计算 LCA。