Наименьший общий предок в двоичном дереве с использованием родительского указателя
Имея значения двух узлов в двоичном дереве, найдите наименьшего общего предка (LCA). Можно предположить, что оба узла существуют в дереве.
Например, рассмотрим двоичное дерево на диаграмме, LCA из 10 и 14 равно 12, а LCA из 8 и 14 равно 8.
Пусть T корневое дерево. Наименьший общий предок между двумя узлами n1 и n2 определяется как наименьший узел в T, который имеет как n1, так и n2 в качестве потомков (где мы позволяем узлу быть потомком самого себя). Источник: Википедия.
Мы обсудили различные подходы к поиску LCA в наборе 1. Поиск LCA упрощается, когда задан родительский указатель, поскольку мы можем легко найти всех предков узла, используя родительский указатель. Ниже приведены шаги, чтобы найти LCA.
- Создайте пустую хеш-таблицу.
- Вставьте n1 и всех его предков в хеш-таблицу.
- Проверьте, существует ли n2 или любой из его предков в хеш-таблице, если да, верните первого существующего предка.
Ниже приведена реализация вышеуказанных шагов.
Выход:
LCA of 10 and 8 is 8
Примечание. В приведенной выше реализации используется вставка двоичного дерева поиска для создания двоичного дерева, но функция LCA предназначена для любого двоичного дерева (не обязательно двоичного дерева поиска). Временная сложность: O(h), где h — высота двоичного дерева, если мы используем хеш-таблицу для реализации решения (обратите внимание, что в приведенном выше решении используется карта, для вставки и поиска которой требуется время O (Log h)). Таким образом, временная сложность приведенной выше реализации составляет O (h Log h). Вспомогательное пространство: O(h) AO(h) время и O(1) дополнительное пространство Решение : Приведенное выше решение требует дополнительного пространства, потому что нам нужно использовать хеш-таблицу для хранения посещенных предков. Мы можем решить проблему за O(1) дополнительного пространства, используя следующий факт: если оба узла находятся на одном уровне и если мы проходим вверх, используя родительские указатели обоих узлов, первым общим узлом на пути к корню будет lca. Идея состоит в том, чтобы найти глубины заданных узлов и переместить указатель более глубокого узла на разницу между глубинами. Как только оба узла достигнут одного уровня, пройдите их вверх и верните первый общий узел. Спасибо Mysterious Mind за предложение такого подхода.
Выход :
LCA of 10 and 22 is 20
Вам также могут быть интересны следующие статьи: Наименьший общий предок в двоичном дереве | Установите 1 младшего общего предка в двоичном дереве поиска. Поиск LCA в двоичном дереве с использованием RMQ Эта статья написана Dheeraj Gupta . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.