Lowest Common Ancestor of a Binary Tree

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

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

Q: Сможешь найти наименьшего общего предка, используя указатели на родителя?

Да. В этом массиве родитель элемента с индексом i — это (i-1)/2 , округлённое вниз. Перемещайте больший из двух индексов к его родителю, пока они не сравняются; больший индекс никогда не является предком меньшего. Для связанных узлов поместите предков p в множество и поднимайтесь от q до первого узла из этого множества.

СреднеОбход деревьев Рекурсия

+10

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

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

Функция

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

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

Ограничения

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

Примеры

Ввод: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
Вывод: 3
Пояснение: 6 — левый потомок 3, а 9 находится ниже 4, справа от 3, поэтому они встречаются в 3. Сравнение значений указывало бы на корень 8: 6 меньше, а 9 больше.

Ввод: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
Вывод: 4
Пояснение: 7 — левый потомок 4, а поддерево 4 включает само 4, поэтому ответ — 4.

Ввод: root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
Вывод: 6
Пояснение: У корня 1 нет левого потомка. У его правого потомка 6 слева находится 3, а справа — 0, поэтому значения сходятся в 6.

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

Если p или q могут отсутствовать, а ответом в таком случае должно быть -1, какой вариант оптимизации нарушается и как всё же завершить задачу за один проход?

Подсказки

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

Открыто 0 из 3

Решение

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

Идите вниз, проверяя каждую сторону

Идея

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

Каждый шаг вниз выполняет поиск по целому поддереву, поэтому h уровней обходятся в O(n·h), а на высоком узком дереве без ограничения глубины — в O(n²). Поиск в узле 8 уже посетил каждый узел ниже 3, а на шаге в узле 3 некоторые из них посещаются снова.

Алгоритм

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

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

    def contains(i, value):
        # Is value somewhere in the subtree at index i?
        if i >= n or root[i] == -1:
            return False
        if root[i] == value:
            return True
        return contains(2 * i + 1, value) or contains(2 * i + 2, value)

    i = 0  # p and q are always inside the subtree at i
    while True:
        if root[i] == p or root[i] == q:
            return root[i]  # one value is here, the other is below it
        left = 2 * i + 1
        p_left = contains(left, p)
        q_left = contains(left, q)
        if p_left and q_left:
            i = left  # both on the left
        elif not p_left and not q_left:
            i = 2 * i + 2  # both on the right
        else:
            return root[i]  # one on each side

Один обход в постфиксном порядке

Идея

Пусть каждое поддерево даст ответ один раз, снизу вверх. find(i) возвращает индекс ответа, если в поддереве с корнем i находятся оба значения, индекс p или q, если в нём находится одно из них, и -1, если в нём нет ни одного.

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

В первом примере 3 получает индекс 3 слева и 10 справа, возвращает собственный индекс 1, а корень передаёт его наверх. Каждый узел посещается один раз: время O(n), рекурсия O(h).

Алгоритм

find(i) возвращает -1 для индекса за пределами конца или значение -1.
Узел со значением p или q возвращает i, не просматривая узлы ниже.
Любой другой узел вычисляет left = find(2*i+1) и right = find(2*i+2). Если оба не равны -1, он возвращает i; иначе — тот, который не равен -1, или -1.
Возвращает root[find(0)].

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

    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 root[i] == -1:
            return -1
        if root[i] == p or root[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 root[find(0)]

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

Сравнение значений с узлом. У дерева нет порядка: в первом примере обход останавливается на корне 8 вместо 3.
Передача вверх true или false вместо индекса. Родитель не может понять, находится ли уже найденный ответ ниже него.
Чтение дочернего узла без проверки длины. У 9 с индексом 10 индексы дочерних узлов — 21 и 22, то есть за пределами последнего элемента.
Возврат find(0), индекса, вместо root[find(0)].
В Lua и R массивы начинаются с 1: сохраняйте индексы узлов с отсчётом от 0 и считывайте root[i + 1].

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

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

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

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

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

Сможешь найти наименьшего общего предка, используя указатели на родителя?

Да. В этом массиве родитель элемента с индексом i — это (i-1)/2, округлённое вниз. Перемещайте больший из двух индексов к его родителю, пока они не сравняются; больший индекс никогда не является предком меньшего. Для связанных узлов поместите предков p в множество и поднимайтесь от q до первого узла из этого множества.

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

Тест #1

Тест #2

Тест #3

Аргументы

root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]
p = 6
q = 9

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