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 . То же правило даёт p , если значения равны. Обход обрабатывает оба случая: он останавливается, как только текущий узел совпадает с одним из значений.

Q: Почему обход останавливается на первом узле, где p и q расходятся?

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

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

+10

Дано бинарное дерево поиска, хранящееся в массиве tree в порядке уровней, и два значения p и q, которые в нём присутствуют. Корень находится по индексу 0, дети узла с индексом i находятся по индексам 2*i+1 (левый) и 2*i+2 (правый), -1 обозначает пустое место, а в конце массива могут быть дополнительные элементы -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 — левый потомок 8, а 15 находится ниже 12, справа от 8. Поднимаясь вверх от каждого из них, мы впервые встречаем узел 8, поэтому это и есть ответ; корень 20 тоже является общим предком, но находится выше.

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

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

+12 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

Выполните поиск по всему дереву, не учитывая порядок

Идея

Сначала разберёмся, как перемещаться по массиву. Узел с индексом i имеет левого потомка с индексом 2*i+1, а правого — с индексом 2*i+2. Потомок существует, только если его индекс находится в пределах массива и значение по этому индексу не равно -1. В массиве [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] у корня 20 есть потомки 8 и 31 с индексами 1 и 2, а у узла 12 с индексом 4 есть потомки 10 и 15 с индексами 9 и 10.

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

Для p = 3 и q = 15 узел 8 получает индекс 3 от левого потомка и индекс 10 от правого, поэтому возвращает сам себя. Корень получает это значение от левого потомка, а от правого — -1, и передаёт 8 выше.

Метод правильный, но он может посетить каждый узел: время работы — 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)]

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

Идея

Теперь воспользуйся порядком. Найти значение можно так, как и следует искать в дереве поиска: начни с корня, иди влево, если значение меньше узла, вправо, если оно больше, и остановись, когда найдёшь его. Этот путь проходит через всех предков значения и больше ни через какие узлы, потому что путь от корня до узла единственный.

Запиши путь для p и путь для q. Оба начинаются от корня и проходят через одни и те же узлы, пока значения не пойдут в разные стороны. Общее начало — это список их общих предков, поэтому последнее общее значение — самое нижнее. Для 3 и 15 пути такие: 20, 8, 3 и 20, 8, 12, 15: у них общие 20, 8, и ответ — 8. Для 12 и 10 это 20, 8, 12 и 20, 8, 12, 10, а ответ — 12.

Каждый путь требует одного шага на уровень, поэтому временная сложность составляет O(h) — здесь не более 14 шагов, сколько бы узлов ни было в дереве. Для двух списков требуется 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 не содержит оба значения; либо одно из них равно v, а узел является предком самого себя. В любом случае v — самый глубокий узел, расположенный выше обоих.

В третьем примере корень 50 находится ниже и 55, и 80, поэтому вы идёте направо к 70. Там 55 меньше, а 80 больше: ответ — 70. Во втором примере вы переходите от 20 к 8, затем к 12, что равно p, и останавливаетесь.

Вы проходите по одному пути от корня, выполняя по одной паре сравнений на каждом уровне, поэтому время работы — 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 проверка p ≤ 12 и q ≤ 12 проходит мимо ответа к 10, и после этого путь возвращает 10 или выходит за пределы дерева. Перемещайтесь только тогда, когда оба значения строго находятся по одну сторону.
Предположение, что p < q. Значения могут идти в любом порядке. Проверяйте оба значения относительно узла или сначала поменяйте их местами так, чтобы p было меньшим.
Забывают, что одно значение может быть предком другого. Тогда ответом будет само это значение, а не его родитель.
Возвращают индекс вместо значения. Функция возвращает tree[i], а не i.
Выполняют поиск по всему дереву. Это даёт правильный ответ, но при этом посещаются все узлы, хотя достаточно пройти по одному пути.
Путают смещение в Lua и R, где массивы начинаются с 1. Оставляйте индексы узлов 0-индексированными для вычисления 2*i+1 и считывайте tree[i + 1].

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

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

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

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

В обычном бинарном дереве значение может находиться где угодно, поэтому приходится искать в обоих поддеревьях каждого узла, и объём работы составляет O(n). В дереве поиска сравнение двух значений со значением узла показывает, в какой стороне находится каждое из них, поэтому ты проходишь по одному пути от корня. Рекурсивный метод для произвольного дерева по-прежнему работает и для дерева поиска, но при этом теряет эту информацию.

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

Да. Узел считается предком самого себя, поэтому, когда p находится выше q, ответ — p. То же правило даёт p, если значения равны. Обход обрабатывает оба случая: он останавливается, как только текущий узел совпадает с одним из значений.

Почему обход останавливается на первом узле, где p и q расходятся?

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

Python

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

Функция

Ограничения

Примеры

Подсказки

Решение

Выполните поиск по всему дереву, не учитывая порядок

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

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

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

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

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