寻找最少在二叉树中的共同祖先o（h^2）换一个

Question

在考虑写一个函数来实现它之前，我试着想一个算法。 h被表示为主父节点与给定节点之间的最大距离。它应该运行在o（h^2）这意味着它应该更容易提出这样一个算法，但我经常发现自己与o（h）算法。当谈到了解我是否真的在做h^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顶点。