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

Question

Я пытался решить проблему, используя алгоритм Тарьяна и один алгоритм с веб-сайта: http://discuss.techinterview.org/default.asp?interview.11.532716.6,, но ни один не ясен.Возможно, мои концепции рекурсии построены неправильно.Пожалуйста, дайте небольшую демонстрацию, чтобы объяснить два приведенных выше примера.У меня есть идея Union Find-структуры данных.

Это выглядит очень интересной проблемой.Так что придется все равно расшифровывать проблему.Подготовка к собеседованиям.

Если есть какая-либо другая логика / алгоритм, пожалуйста, поделитесь.

Answer 1

Алгоритм LCA пытается сделать простую вещь: выяснить пути от двух рассматриваемых узлов до корня.Теперь эти два пути будут иметь общий суффикс (при условии, что путь заканчивается в корне).LCA является первым узлом, где начинается суффикс.

Рассмотрим следующее дерево:

              r * 
               / \
            s *   *
             / \
          u *   * t
           /   / \
          * v *   *
             / \
            *   *

Чтобы найти LCA (u, v), действуем следующим образом:

• Путь от u к корню: путь (u, r) = usr
• Путь от v к корню: путь (v, r) = vtsr

Теперь мы проверяем наличиеобщий суффикс:

• общий суффикс: 'sr'
• Поэтому LCA (u, v) = первый узел суффикса = s

Обратите внимание нафактические алгоритмы не до самого корня.Они используют структуры данных Disjoint-Set для остановки, когда достигают s.

объясняется отличный набор альтернативных подходов здесь .

Answer 2

Поскольку вы упомянули собеседования при приеме на работу, я подумал о вариации этой проблемы, когда вы ограничены использованием памяти O (1).

В этом случае рассмотрим следующий алгоритм:

1) Сканирование дерева от узла u до корня, нахождение длины пути L (u)

2) Сканирование дерева от узла v до корня, нахождение длины пути L (v)

3) Рассчитать разницу в длине пути D = | L (u) -L (v) |

4) Пропустить D-узлы на более длинном пути от корня

5)Идите вверх по дереву параллельно от двух узлов, пока не дойдете до одного и того же узла

6) Верните этот узел как LCA

Answer 3

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

Let A and B begin as the nodes in question.
seen := set containing the root node
while A is not root:
    add A to seen
    A := A's parent
while B is not in seen:
    B := B's parent
B is now the lowest common ancestor.

Другой метод состоит в том, чтобы вычислить полный путь к комнате для каждого узла, а затем сканировать справа, ища общий суффикс. Его первый элемент - LCA. Какой из них быстрее, зависит от ваших данных.

Если вам понадобится найти LCA для многих пар узлов, вы можете сделать различные компромиссы между пространством и временем:

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

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