graph - 変更のためにo（h ^ 2）を使用してバイナリツリーで最小共通祖先を見つける

Question

それを実現する関数を書くことを考える前に、アルゴリズムを考えようとします。h は、メインの親から特定のノードまでの最大距離として示されます。o(h^2) で実行する必要があります。つまり、そのようなアルゴリズムを考え出すのは簡単ですが、私は常に o(h) アルゴリズムを使用しています。実際に ah^2 操作を行っているかどうかを理解することになると、私も混乱します。私は本当にリードを使うことができました。

Answer 1

The simplest algorithm for LCA would run in O(h^2) — make two nested loops, one running over all ancestors of first vertex, the other running over all ancestors of the second, and inside the loop just compare them.

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

So, go up from the first given vertex, that is go through all its ancestors. For each its ancestor a1, go from the second given vertex up to root and check whether you meet the a1 vertex on the way.