目前，我正在开发一个程序，其中一个步骤是检查一个叶子 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 数据结构。
希望这可以帮助！