Нахождение ближайшего родителя для двух узлов

Question

Каков наилучший способ найти ближайших родителей для двух заданных узлов в дереве?
Так что если у меня есть:

                1
              /   \ 
             2     3
            / \   / \
           4  5  6   7  

ближайший родитель для 5 и 6 будет один.
Спасибо

Answer 1

Эта проблема называется проблемой самого низкого общего предка (LCA).(Google it)

На один запрос можно ответить, просто взбираясь по их parent ссылкам, пока они не встретятся:

Первый шаг - позволить нижнему узлу подняться, пока они не окажутся вто же самое height.

Второй шаг - позволить им подняться одновременно, пока они не встретятся в одном узле.

Тогда этот узел является LCA этих двух узлов.

Если вам нужно обрабатывать несколько запросов, вам нужно использовать более продвинутый алгоритм.Наиболее эффективный по времени алгоритм использует O (n) время для предварительной обработки и O (1) время для каждого запроса, где n - общее количество узлов вдерево.