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

Метод 1: поиск в глубину (DFS).
Один эффективный способ найти LCA — использовать алгоритм поиска в глубину. Вот как это работает:

1. Начните обход двоичного дерева с корневого узла.
2. Проверьте, равен ли какой-либо из заданных узлов текущему узлу. Если да, верните текущий узел как LCA.
3. Рекурсивно искать LCA в левом и правом поддеревьях.
4. Если оба поддерева возвращают ненулевое значение, это означает, что данные узлы находятся на противоположных сторонах текущего узла, что делает текущий узел LCA.
5. Если только одно поддерево возвращает ненулевое значение, это означает, что оба узла присутствуют в этом поддереве. Верните ненулевое значение в качестве LCA.
6. Если оба поддерева возвращают нулевое значение, верните нулевое значение.

Вот упрощенная реализация на Python:

def find_LCA(root, node1, node2):
    if root is None:
        return None
    if root == node1 or root == node2:
        return root
    left_LCA = find_LCA(root.left, node1, node2)
    right_LCA = find_LCA(root.right, node1, node2)
    if left_LCA and right_LCA:
        return root
    elif left_LCA:
        return left_LCA
    else:
        return right_LCA

Метод 2: поиск в ширину (BFS)
Другой подход к поиску LCA — использование алгоритма поиска в ширину. Вот общий обзор:

1. Выполнение обхода двоичного дерева по уровням с использованием очереди.
2. Во время перемещения отслеживайте отношения родитель-потомок, сохраняя родительский узел для каждого встреченного узла.
3. Как только вы встретите любой из заданных узлов, остановите обход и сохраните путь от корня до этого узла.
4. Найдите LCA, сравнив два пути от корня до заданных узлов.

Вот упрощенная реализация на Python:

from collections import deque
def find_LCA(root, node1, node2):
    if root is None:
        return None
    queue = deque([(root, None)])
    path = {root: None}
    while queue:
        current, parent = queue.popleft()
        if current == node1 or current == node2:
            break
        if current.left:
            queue.append((current.left, current))
            path[current.left] = current
        if current.right:
            queue.append((current.right, current))
            path[current.right] = current
    path_to_node1 = set()
    while node1:
        path_to_node1.add(node1)
        node1 = path[node1]
    while node2:
        if node2 in path_to_node1:
            return node2
        node2 = path[node2]
    return None

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