使用 o(h^2) 在二叉树中查找最小共同祖先以进行更改

Question

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

Answer 1

最简单的 LCA 算法将 运行 in O(h^2) — 进行两个嵌套循环，一个 运行ning 遍历第一个顶点的所有祖先，另一个 运行ning在第二个的所有祖先上，在循环内比较它们。

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个顶点。