Наименьший общий предок между двумя узлами двоичного дерева (рекурсивный подход)

Бесплатный 5-дневный мини-курс: https://backtobackswe.com
Попробуйте нашу полную платформу: https://backtobackswe.com/pricing
📹 Интуитивно понятные видеообъяснения
🏃 Запускайте код по мере обучения
💾 Сохраняйте прогресс
❓Новые, ранее не рассматривавшиеся вопросы
🔎 Получить все решения

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

Подход

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

Алгоритм

Суть в том, что мы хотим получить корень в узле, а затем искать слева и справа любой из двух заданных узлов.

Если мы видим какой-либо узел, мы его возвращаем. Если же узел не найден при поиске по поддереву, будет возвращено значение null, и оно будет поднято наверх.

После того, как мы выполним поиск слева и справа, мы спрашиваем себя, что означают наши результаты.

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

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

Если и справа, и слева результаты не равны нулю, мы нашли наш LCA.

Почему?

Мы знаем, что это, по крайней мере, предок, но мы точно знаем, что это низший общий предок, потому что мы пошли снизу вверх, и всё, что мы встретим, будет LCA, и оно поднимется наверх.

Сложности

Время: O(n)

В процессе поиска мы будем использовать всё дерево. В дереве n узлов, и в каждом узле мы выполняем O(1) операций. Хотя вызовов не ровно n, мне нужно это перепроверить... Мне нужно решить рекуррентное соотношение, ну да ладно... мы знаем, что оно останется линейным в асимптотике.

Пространство: O(h)

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

++++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Тушар Рой:    / tusharroy2525  

GeeksForGeeks:    / @geeksforgeeksvideos  

Джарвис Джонсон:    / vsympathyv  

Успех в технологиях:    / @successintech