Что не так с этим алгоритмом наименьшего общего предка?

В ходе собеседования мне задали следующий вопрос:

При наличии корневого узла (в правильно сформированном двоичном дереве) и двух других узлов (которые гарантированно находятся в дереве и также различаются), возвращают наименьшего общего предка двух узлов.

Я не знал ни одного наименее распространенного алгоритма предка, поэтому попытался создать его на месте. Я создал следующий код:

def least_common_ancestor(root, a, b):
    lca = [None]
    def check_subtree(subtree, lca=lca):
        if lca[0] is not None or subtree is None:
            return 0

        if subtree is a or subtree is b:
            return 1
        else:
            ans = sum(check_subtree(n) for n in (subtree.left, subtree.right))

        if ans == 2:
            lca[0] = subtree
            return 0

        return ans

    check_subtree(root)

    return lca[0]


class Node:
    def __init__(self, left, right):
        self.left = left
        self.right = right

Я попробовал следующие тесты и получил ответ, который ожидал:

a = Node(None, None)
b = Node(None, None)

tree = Node(Node(Node(None, a), b), None)
tree2 = Node(a, Node(Node(None, None), b))
tree3 = Node(a, b)

но мой интервьюер сказал мне, что "существует класс деревьев, для которого ваш алгоритм возвращает None". Я не мог понять, что это было, и я провалил интервью. Я не могу вспомнить случай, когда алгоритм добрался бы до нижней части дерева без ans когда-либо становился 2 - что я пропускаю?

Источник

2 ответа

Решение

Вы забыли учесть случай, когда a является прямым предком b, или наоборот. Вы прекращаете поиск, как только находите какой-либо узел и возвращаетесь 1, так что вы никогда не найдете другой узел в этом случае.

Вам было дано правильно сформированное двоичное дерево поиска; Одним из свойств такого дерева является то, что вы можете легко найти элементы, основываясь на их относительном размере к текущему узлу; меньшие элементы идут в левое поддерево, большие - в правое. Таким образом, если вы знаете, что оба элемента находятся в дереве, вам нужно только сравнить ключи; как только вы найдете узел, который находится между двумя целевыми узлами или равен одному из них, вы обнаружите наименьшего общего предка.

Ваши примеры узлов никогда не включали ключи, хранящиеся в дереве, поэтому вы не можете использовать это свойство, но если вы это сделали, вы бы использовали:

def lca(tree, a, b):
    if a.key <= tree.key <= b.key:
        return tree
    if a.key < tree.key and b.key < tree.key:
        return lca(tree.left, a, b)
    return lca(tree.right, a, b)

Если дерево является просто "обычным" двоичным деревом, а не деревом поиска, ваша единственная возможность - найти пути для обоих элементов и найти точку, в которой эти пути расходятся.

Если ваше двоичное дерево поддерживает родительские ссылки и глубину, это можно сделать эффективно; просто поднимитесь по глубине двух узлов, пока не окажетесь на одной и той же глубине, затем продолжайте вверх от обоих узлов, пока не найдете общий узел; это наименее распространенный предок.

Если у вас нет этих двух элементов, вам придется найти путь к обоим узлам с помощью отдельного поиска, начиная с корня, а затем найти последний общий узел в этих двух путях.

Источник

Вы пропускаете случай, когда a является предком b,

Посмотрите на простой встречный пример:

    a
  b  None

a также дается как rootи при вызове функции вы вызываете check_subtree(root), который aЗатем вы обнаруживаете, что это то, что вы ищете (в предложении stop, которое возвращает 1), и возвращаете 1 безотлагательно без установки lca как и должно было быть.

Источник
Другие вопросы по тегам