Найти наименьшего общего предка двух узлов дерева, без ссылки на корень?

Question

class TreeNode {
    TreeNode parent;
    TreeNode left;
    TreeNode right;

    // other data fields omitted - not relevant
}

Вам дано два узла p, а также qКак вы находите самого низкого общего предка? (Предположим, они оба принадлежат очень большому дереву)

У вас нет ссылки на корень дерева.

Какой самый эффективный способ сделать это? До сих пор у меня была единственная идея:

(1) выбрать узел р (неважно, какой)

(2) искать левое поддерево p, если см. Q, вернуть p

(3) в противном случае ищите правильное поддерево p, если смотрите q, верните p

(4) в противном случае перейдите на один уровень к родительскому и ищите поддерево, которое не содержит p, если найдено q, верните родительское

(5) иначе, снова поднимитесь на один уровень, повторите (4) (ищите поддерево, которое не содержит этого родителя)

Это кажется крайне неэффективным. Есть лучший алгоритм?

Answer 1

Есть ли у вас экстремальные ограничения на объем оперативной памяти, которую вы можете использовать? Если нет, я бы предложил что-то вроде этого:

visited_nodes = {}    // something like a HashMap, with O(1) insert and retrieval
node1 = p
node2 = q

while True:
    if node1 == null and node2 == null:    // the nodes don't seem to be in same tree
        return null    // or failure or anything like that

    if node1 is not null:
        if node1 in visited_nodes:    // node1 must be lowest common ancestor
            return node1
        else:
            visited_nodes.insert(node1)    // remember that we've seen this node
            node1 = node1.getParent()

    if node2 is not null:
        if node2 in visited_nodes:    // node2 must be lowest common ancestor
            return node2
        else:
            visited_nodes.insert(node2)    // remember that we've seen this node
            node2 = node2.getParent()

Интуитивная идея заключается в следующем. Мы начинаем с обоих узлов одновременно. На каждой итерации цикла мы делаем один шаг вверх от обоих узлов. Всякий раз, когда мы видим узел, мы помещаем его в нашу карту (которая должна иметь O(1) вставку и поиск / проверку, если он уже там). Когда мы сталкиваемся с узлом, который мы уже добавили на карту, это должно быть нашим решением.

Этот код никогда не должен работать больше, чем max(d_p, d_q) итерации, где d_p а также d_q обозначить уровни глубины в дереве, p а также q на, соответственно. Это будет особенно большим преимуществом, если оба узла окажутся довольно близко к корню. Это также означает, что код работает даже для бесконечного дерева (тогда как ваше решение застрянет в бесконечном цикле).