Нахождение наименьшего общего предка в двоичном дереве с помощью o(h^2) для изменения

Question

Прежде чем подумать о написании функции для ее выполнения, я попытаюсь придумать алгоритм. h обозначается как максимальное расстояние между основным родителем и данным узлом. Он должен работать в o(h^2), что означает, что такой алгоритм должен быть проще, но я постоянно нахожусь с алгоритмом o(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 вершина в пути.