Алгоритм: Найти общих предков в дереве

Алгоритм: Найти общих предков в дереве (LCA)

Определение и примеры

LCA (Lowest Common Ancestor) - наименьший общий предок двух узлов. Это узел, который находится на наибольшей глубине и является предком обоих узлов.

Пример дерева:
        3
       / \
      5   1
     / \
    6   2
       / \
      7   4

LCA(5, 1) = 3
LCA(5, 4) = 3
LCA(6, 2) = 5
LCA(2, 4) = 2

Решение 1: Рекурсивный поиск (DFS)

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Рекурсивный поиск LCA
    
    Идея:
    - Если текущий узел это p или q - возвращаем его
    - Ищем p и q в левом и правом поддеревьях
    - Если оба найдены - текущий узел это LCA
    - Если найден только один - возвращаем его
    - Если ничего не найдено - возвращаем None
    """
    if root is None:
        return None
    
    # Если нашли один из узлов - возвращаем
    if root.val == p.val or root.val == q.val:
        return root
    
    # Ищем в левом и правом поддеревьях
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # Если оба найдены - текущий узел это LCA
    if left and right:
        return root
    
    # Если найден только один - возвращаем его
    return left if left else right


# Пример использования
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

p = root.left  # узел 5
q = root.right  # узел 1

result = lowestCommonAncestor(root, p, q)
print(f"LCA(5, 1) = {result.val}")  # Output: 3

Анализ сложности:

• Время: O(n) - посещаем каждый узел один раз
• Память: O(h) где h - высота дерева (рекурсивный стек вызовов)
  • Лучший случай: O(log n) для сбалансированного дерева
  • Худший случай: O(n) для несбалансированного (цепочка)

---

Решение 2: С хранением пути (если родитель известен)

def lowestCommonAncestorWithParent(p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Если у узлов есть ссылка на родителя
    
    Идея:
    - Получаем пути от обоих узлов до корня
    - Ищем первый общий узел
    """
    visited = set()
    
    # Идем от p к корню и запоминаем узлы
    current = p
    while current:
        visited.add(current.val)
        current = current.parent
    
    # Идем от q к корню и ищем первый уже виденный узел
    current = q
    while current:
        if current.val in visited:
            return current
        current = current.parent
    
    return None


# Если у узлов есть parent
class TreeNodeWithParent:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

Анализ сложности:

• Время: O(h) где h - высота дерева
• Память: O(h) для хранения visited set

---

Решение 3: Бинарный поиск (для BST)

def lowestCommonAncestorBST(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Специальный случай для Binary Search Tree
    
    Идея:
    - Если оба узла меньше текущего - ищем в левом поддереве
    - Если оба больше - ищем в правом поддереве
    - Иначе текущий узел это LCA
    """
    if root is None:
        return None
    
    # Убедимся что p.val < q.val
    if p.val > q.val:
        p, q = q, p
    
    # Если оба меньше - ищем в левом поддереве
    if q.val < root.val:
        return lowestCommonAncestorBST(root.left, p, q)
    
    # Если оба больше - ищем в правом поддереве
    elif p.val > root.val:
        return lowestCommonAncestorBST(root.right, p, q)
    
    # Иначе текущий узел - LCA
    else:
        return root


# Или итеративно:
def lowestCommonAncestorBSTIterative(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """Итеративная версия для BST"""
    current = root
    
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            # Один слева, один справа (или совпадает)
            return current
    
    return None

Анализ сложности (для BST):

• Время: O(log n) в среднем, O(n) в худшем (несбалансированное дерево)
• Память: O(1) для итеративной версии, O(h) для рекурсивной

---

Решение 4: Бинарная подъёмка (для больших деревьев)

def preprocess_tree(root: TreeNode, max_power: int = 20):
    """
    Предварительная обработка дерева для быстрого LCA поиска
    Используется Binary Lifting техника
    """
    parent = {}
    depth = {}
    
    def dfs(node, par, d):
        if node is None:
            return
        
        parent[node.val] = [par] * max_power
        depth[node.val] = d
        
        if node.left:
            dfs(node.left, node.val, d + 1)
        if node.right:
            dfs(node.right, node.val, d + 1)
    
    dfs(root, None, 0)
    
    # Заполняем таблицу прыжков
    for i in range(1, max_power):
        for node_val in parent:
            if parent[node_val][i-1]:
                parent[node_val][i] = parent[parent[node_val][i-1]][i-1]
            else:
                parent[node_val][i] = None
    
    return parent, depth


def queryLCA(p_val, q_val, parent, depth):
    """Поиск LCA с использованием бинарной подъёмки"""
    # Приводим узлы на одну глубину
    if depth[p_val] < depth[q_val]:
        p_val, q_val = q_val, p_val
    
    diff = depth[p_val] - depth[q_val]
    
    # Поднимаем p_val на уровень q_val
    for i in range(20):
        if (diff >> i) & 1:
            p_val = parent[p_val][i]
            if p_val is None:
                break
    
    if p_val == q_val:
        return p_val
    
    # Поднимаем обоих до LCA
    for i in range(19, -1, -1):
        if parent[p_val][i] != parent[q_val][i]:
            p_val = parent[p_val][i]
            q_val = parent[q_val][i]
    
    return parent[p_val][0]

Анализ сложности:

• Предобработка: O(n log n)
• Один запрос: O(log n)
• Память: O(n log n)
• Использование: когда много запросов LCA

---

Сравнение подходов

---

Полное решение с тестами

def test_lca():
    """Тестирование всех решений"""
    
    # Создание тестового дерева
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(4)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)
    
    test_cases = [
        (5, 1, 3),      # LCA(5, 1) = 3
        (5, 4, 5),      # LCA(5, 4) = 5
        (6, 2, 5),      # LCA(6, 2) = 5
        (2, 4, 2),      # LCA(2, 4) = 2
        (0, 8, 1),      # LCA(0, 8) = 1
    ]
    
    print("Тестирование решений LCA:")
    for p_val, q_val, expected in test_cases:
        p = find_node(root, p_val)
        q = find_node(root, q_val)
        
        result = lowestCommonAncestor(root, p, q)
        print(f"LCA({p_val}, {q_val}) = {result.val} (ожидается {expected}) "
              f"{'✓' if result.val == expected else '✗'}")


def find_node(root: TreeNode, val: int) -> TreeNode:
    """Вспомогательная функция для поиска узла по значению"""
    if root is None:
        return None
    if root.val == val:
        return root
    left = find_node(root.left, val)
    return left if left else find_node(root.right, val)


if __name__ == "__main__":
    test_lca()

Итоги

1. Простое решение: рекурсивный DFS - O(n) время, O(h) память
2. Оптимальное для BST: использовать свойства BST - O(log n)
3. Для много запросов: бинарная подъёмка - O(log n) на запрос после O(n log n) обработки
4. Если есть parent: путь до корня - O(h) время, простая реализация