Lowest Common Ancestor of a BST

Q: Какова временная сложность поиска наименьшего общего предка в BST?

Обход от корня следует по одному пути, поэтому для дерева глубины h он занимает время O(h) и дополнительную память O(1). Для сбалансированного дерева это O(log n); для дерева, имеющего форму одного пути, — O(n).

Q: Чем отличается LCA в двоичном дереве поиска от LCA в двоичном дереве?

В обычном бинарном дереве значение может находиться где угодно, поэтому можно проверить каждый узел — это O(n) работы. В дереве поиска сравнение двух значений со значением в узле позволяет понять, с какой стороны находится каждое из них, поэтому от корня вы следуете по одному пути.

Q: Может ли узел быть своим собственным наименьшим общим предком?

Да. Узел считается предком самого себя, поэтому, когда p находится выше q , ответом будет p , а если два значения равны, ответом будет это значение.

СреднеДвоичное дерево поиска

+10

Дано бинарное дерево поиска, хранящееся в массиве в порядке кучи tree: корень находится по индексу 0, дочерние узлы элемента с индексом i — по индексам 2*i+1 (левый) и 2*i+2 (правый), а -1 обозначает пустое место. Все значения в левом поддереве узла меньше значения этого узла, а все значения в правом поддереве больше.

Напишите функцию lowestCommonAncestor, которая возвращает значение наименьшего общего предка значений p и q, присутствующих в дереве: самого глубокого узла, в поддереве которого находятся оба значения. Узел является частью собственного поддерева, поэтому, если p находится выше q, ответом будет p.

Функция

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

treeinteger-array: двоичное дерево поиска в порядке уровней, где -1 обозначает пустое место
pinteger: первое значение, которое нужно найти
qinteger: второе значение для поиска
Возвращаетinteger: значение самого глубокого узла, в поддереве которого есть и p, и q

Ограничения

1 ≤ tree.length ≤ 32767
Каждый tree[i] равен -1 или является значением, для которого выполняется 0 ≤ tree[i] ≤ 10⁵.
tree[0] никогда не равно -1, поэтому в дереве есть как минимум один узел.
Массив может заканчиваться дополнительными элементами -1 после последнего узла.
Оба потомка пустого места тоже пусты, а глубина не превышает 14.
Дерево является корректным двоичным деревом поиска, поэтому все его значения уникальны.
p и q — это значения узлов дерева. Они могут идти в любом порядке и могут быть равны.

Примеры

Ввод: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
Вывод: 8
Пояснение: Поднимаясь от 3 и от 15, оба узла первыми достигают 8: 3 — его левый потомок, а 15 находится ниже 12 справа от него. Корень 20 тоже является общим предком, но расположен выше.

Ввод: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Вывод: 12
Пояснение: 10 — левый потомок 12, а узел считается своим собственным предком, поэтому 12 содержит оба значения, а ниже него их нет. Здесь p — большее значение.

Ввод: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Вывод: 70
Пояснение: Оба значения больше корня 50, поэтому оба находятся справа от него. На узле 70 их пути расходятся: 55 меньше и находится слева, ниже 60, а 80 больше.

Дополнительный вопрос

Что бы ты изменил, если бы p или q могли отсутствовать в дереве, и в таком случае функция должна была бы возвращать -1?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Дерево поиска показывает для каждого узла, где находится значение: меньшие значения — слева, большие — справа. Начни с корня и двигайся в сторону, где находятся оба значения. Первый узел, в котором они перестают находиться с одной стороны, и есть ответ; до него можно добраться по одному пути.

Поиск по всему дереву без учета порядка

Идея

Этот метод работает с любым двоичным деревом. Рекурсивная функция find(i) сообщает, что хранится в поддереве с корнем в i. Узел, хранящий p или q, сообщает о себе: если другое значение находится ниже него, это и есть ответ, а если нет, узел выше увидит оба значения. Любой другой узел обращается к обоим дочерним узлам. Если оба что-то сообщают, p и q находятся по разные стороны, и этот узел — место, где они встречаются; если что-то сообщает только один, передайте это выше.

Для 3 и 15 узел 8 получает индекс 3 от левого потомка и индекс 10 от правого и сообщает о себе. Он может посетить каждый узел: время O(n), а для рекурсии требуется O(h).

Алгоритм

Напиши find(i). Если позиция с индексом i пуста (за концом массива или -1), верни -1.
Если tree[i] — это p или q, верни i.
Вызови find для 2*i+1 и 2*i+2. Если оба вызова что-то нашли, верни i.
В противном случае верни результат того вызова, который что-то нашёл, или -1.
Верни tree[find(0)].

def lowestCommonAncestor(tree, p, q):
    n = len(tree)

    def find(i):
        # In the subtree at index i: the index of the answer if both values are
        # inside, the index of the one that is, or -1 when neither is.
        if i >= n or tree[i] == -1:
            return -1
        if tree[i] == p or tree[i] == q:
            return i
        left = find(2 * i + 1)
        right = find(2 * i + 2)
        if left != -1 and right != -1:
            return i  # one value on each side: this node is the answer
        return left if left != -1 else right

    return tree[find(0)]

Сравните два пути поиска

Идея

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

Запишите оба пути. Они проходят через одни и те же узлы, пока не разойдутся, поэтому общая начальная часть содержит общих предков, а её последнее значение — наименьшее из них. Для 3 и 15 пути таковы: 20, 8, 3 и 20, 8, 12, 15: общая часть — 20, 8, поэтому ответ — 8. Каждый обход делает один шаг на каждом уровне: время O(h), а для списков требуется O(h) памяти.

Алгоритм

Напиши path(target): начни с индекса 0, запиши tree[i], остановись, когда он станет равен target, иначе перейди к 2*i+1, если target меньше, и к 2*i+2, если оно больше.
Построй путь к p и путь к q.
Пройди по обоим спискам от начала и верни последнее общее для них значение.

def lowestCommonAncestor(tree, p, q):
    def path(target):
        # The values met on the way from the root down to target.
        values = []
        i = 0
        while True:
            values.append(tree[i])
            if tree[i] == target:
                return values
            i = 2 * i + 1 if target < tree[i] else 2 * i + 2

    to_p, to_q = path(p), path(q)
    # Both paths start at the root; the answer is the last value they share.
    answer = to_p[0]
    for a, b in zip(to_p, to_q):
        if a != b:
            break
        answer = a
    return answer

Спускайтесь вниз, пока значения не разделятся

Идея

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

В противном случае одно значение меньше, а другое больше, поэтому ни один потомок v не содержит оба значения, или одно из них равно v, который является предком самого себя. В любом случае v — самый нижний узел, расположенный выше обоих. В третьем примере 50 меньше обоих значений, поэтому нужно идти направо, к 70, где 55 меньше, а 80 больше. Одна пара сравнений на уровень дает время O(h) и память O(1).

Алгоритм

Начните с индекса i = 0.
Прочитайте v = tree[i].
Если p < v и q < v, перейдите к 2*i+1 и повторите.
Если p > v и q > v, перейдите к 2*i+2 и повторите.
В противном случае верните v.

def lowestCommonAncestor(tree, p, q):
    i = 0  # start at the root
    while True:
        value = tree[i]
        if p < value and q < value:
            i = 2 * i + 1  # both are smaller: the answer is on the left
        elif p > value and q > value:
            i = 2 * i + 2  # both are larger: the answer is on the right
        else:
            return value  # they split here, or one of them is this node

Ловушки и крайние случаи

Использование ≤ и ≥ в проверках перемещения. При p = 12 и q = 10 обход проходит мимо 12 к 10, а затем возвращает 10 или выходит за пределы дерева.
Предположение, что p < q. Во втором примере значение p больше. Сравните оба значения с узлом или сначала поменяйте их местами.
Возврат индекса вместо значения. Ответ — tree[i], а не i.
В Lua и R массивы начинаются с 1. Оставляйте индексы узлов отсчитываемыми от 0 для арифметики 2*i+1 и обращайтесь к tree[i + 1].

Частые вопросы3

Какова временная сложность поиска наименьшего общего предка в BST?

Обход от корня следует по одному пути, поэтому для дерева глубины h он занимает время O(h) и дополнительную память O(1). Для сбалансированного дерева это O(log n); для дерева, имеющего форму одного пути, — O(n).

Чем отличается LCA в двоичном дереве поиска от LCA в двоичном дереве?

В обычном бинарном дереве значение может находиться где угодно, поэтому можно проверить каждый узел — это O(n) работы. В дереве поиска сравнение двух значений со значением в узле позволяет понять, с какой стороны находится каждое из них, поэтому от корня вы следуете по одному пути.

Может ли узел быть своим собственным наименьшим общим предком?

Да. Узел считается предком самого себя, поэтому, когда p находится выше q, ответом будет p, а если два значения равны, ответом будет это значение.

def lowestCommonAncestor(tree, p, q):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

Ожидаемый вывод

Lowest Common Ancestor of a BST

Функция

Ограничения

Примеры

Подсказки

Решение

Поиск по всему дереву без учета порядка

Сравните два пути поиска

Спускайтесь вниз, пока значения не разделятся

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи