问题标签 [least-common-ancestor]

给定下面的类和接口，我想知道为什么隐式转换：

是不可能的。我试过了

但后来我不能使用GetById和GetAll方法。我感谢任何帮助或提示。谢谢你。

图中有 N 个节点，由 N-1 条边连接。从一个节点到任何其他节点恰好有 1 条最短路径。节点从 1 到 N 编号。给定 Q 个查询，它们告诉源节点和目标节点。在经过这些 Q 条路径后找到访问次数最多的节点。例如，假设 Q=3 和 3 个查询是：

所以从节点 1 到节点 5，然后从节点 2 到节点 4，然后从节点 3 到节点 1。最后，在 Q 次查询之后找到访问次数最多的节点。找到每条路径并增加每个访问的节点计数是一种幼稚的方法。面试官让我优化一下。

我们需要在合并两个历史数据更改时获得 LCA，每个历史中的历史和节点都非常多；随着分支和合并的发生——所以要找到从 2 个点开始的 2 个历史的 LCA，我们必须向后搜索任何历史，而不仅仅是沿着两个给定的历史往回走。

已发布的查找 LCA 的方法似乎假设对所有节点进行预扫描作为第一阶段，我们希望避免这种情况。

研究了对历史中的每个节点使用矢量时钟 - 那么我们根本不需要进行任何搜索，只需知道两个起始节点的 VC 就会给我们 LCA 的 VC。但是 VC 存在问题，因为我们有大量动态的历史和节点。

我们使用了一个简单的标量计数器（类似于逻辑时钟，在其他地方使用）而不是 VC，我们确实需要进行部分搜索，但预计复杂度会更低。该代码似乎工作正常。我想知道是否有其他人做过类似的事情或者可以看到一些问题。

我用谷歌搜索并试图在图中找到关于 LCA（两个节点）的信息，但不幸的是，我没有找到太多描述性和可理解的内容。

那么请有人可以在图表中详细说明 LCA（有向和无向）吗？

所以我试图在python中使用Euler tour和RMQ和稀疏表来实现LCA。如果我从树的左侧插入数字，我的代码工作正常。构建树的代码是：

节点类有数据，left_child 和 right_child：

然后我有一个用于构建树的树类：

最后，我得到了一个 LCA 类，它主要包含构建稀疏表的函数，然后在稀疏表上执行 RMQ，然后是执行欧拉遍历部分的函数，最后是查找 LCA 的函数。

我的驱动程序代码如下：

所以，我的树应该是这样的：

现在，如果我尝试找到 LCA(8, 9) 或 LCA(4, 3)，我会得到正确的输出，但每当我尝试给出 LCA(6, 7) 或 LCA(3, 7) 时，它总是保持返回 2 作为应该分别返回 3 和 3 的答案。

我不知道错误在哪里，从我的角度来看，它看起来还不错。

当我们想要返回单个节点而不是两个节点时，为什么要返回右或左？

我意识到即使左右不是同一个TreeNode，布尔值“左右”也会返回true。此外，没有编写比较函数。那有必要吗？