Поиск наименее общего предка в двоичном дереве с 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 по пути.