Самый низкий общий предок двоичного дерева

Сложность: 🟡 Средняя

ℹ️ Описание

Вам дано двоичное дерево. Найдите наименьшего общего предка (LCA) двух заданных узлов в дереве.

Согласно определению LCA в Википедии: «Наименьший общий предок определяется между двумя узлами p и q как самый нижний узел в дереве T, который имеет как p, так и q в качестве потомков (где мы позволяем узлу быть потомком самого себя).»

⚠️ Ограничения

— Количество узлов в дереве находится в диапазоне от 2 до 10^5.
— Значения каждого узла в дереве находятся в диапазоне от -10^9 до 10^9.
— Значения всех узлов в дереве уникальны.
— p != q.
— p и q всегда существуют в дереве.


1️⃣ Пример

Входные параметры: дерево выше, p = 5, q = 1.

Ответ: 3

Объяснение: LCA узлов 5 и 1 равен 3.

2️⃣ Пример

Входные параметры: дерево выше, p = 5, q = 4.

Ответ: 5

Объяснение: LCA узлов 5 и 4 равен 5, поскольку узел может быть потомком самого себя согласно определению LCA.


✅ Решение

Решение этой задачи достаточно интуитивно. Сначала мы пройдем по дереву вглубь. В тот момент, когда встретится любой из узлов p или q, вернем логический флаг. Флаг помогает определить, нашли ли мы нужные узлы на каком-либо из путей. Тогда наименьшим общим предком будет узел, для которого обе рекурсии поддерева возвращают флаг true. Это также может быть узел, который сам является одним из узлов p или q и для которого одна из рекурсий поддерева возвращает флаг true.

Для реализации будем использовать рекурсивный подход с замыканием для хранения переменной lca.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

O(n) — так как в худшем случае нам нужно посетить все n узлов в дереве.

По памяти

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

#tries #medium