目前，我正在开发一个程序，其中一个步骤是检查叶子 c 是否与二叉树 T 中的另外两个叶子 a 和 b 位于同一子树中。我目前的方法如下：首先，在T中找到每对叶子的LCA，并将其存储在字典中。然后，对于树中的每个节点，找到作为其后代的所有叶子，并将其存储在字典中。然后，当我需要确定 c 是否与 a 和 b 位于同一子树中时，我找到 a 和 b 的 LCA，并检查 c 是否是它的后代。
我需要为许多不同的对 a 和 b 运行此步骤，并在具有多达 600 个叶子的二叉树上执行此操作，那么是否有更快的算法，或者使用更少内存的算法，可以执行相同的任务？谢谢。
这里有一个有用的观察可能对你有所帮助：包含叶子 a 和 b 的最小子树是根植于 LCA（a， b） 的子树。 这意味着您可以通过检查 c 是否是 LCA（a， b） 的后代来测试 c 是否在子树中。一种方法如下：计算LCA（LCA（a，b），c）。 如果 c 在此子树中，则 LCA（LCA（a， b）， c） = LCA（a， b）。 否则，它将是其他节点。这给出了一个很好的算法：
返回 LCA（LCA（a， b）， c） = LCA（a， b） 是否。
使用快速的 LCA 数据结构也可能有所帮助。您提到了预先计算树中所有节点对的 LCA，但有更快的选择。特别是，有一些不错的算法，在 O（n） 预处理时间内，可以在时间 O（1） 中返回树中两个节点的 LCA。如果您提前知道这些对，请查看 Tarjan 的离线 LCA 算法;如果没有，请查找 Fischer-Heun LCA 数据结构。
希望这有帮助！