graph - 用 o(h^2) 在二叉树中找到最小的共同祖先进行更改

Question

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

Answer 1

最简单的 LCA 算法将在O(h^2)其中运行——创建两个嵌套循环，一个运行在第一个顶点的所有祖先上，另一个运行在第二个顶点的所有祖先上，然后在循环内只比较它们。

a1 = a  // a is the first given vertes
while a1 != nil   // assume root's parent is nil
    a2 = b  // b is the second given vertex
    while a2 != nil 
        if (a1 == a2) 
            compare with current-best solution
        a2 = a2.parent
   a1 = a1.parent

所以，从第一个给定的顶点开始，即经过它的所有祖先。对于它的每一个祖先a1，从第二个给定的顶点到根并检查你是否a1在途中遇到顶点。