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

Метод 1: рекурсивное решение
Один из наиболее простых подходов к поиску LCA в двоичном дереве — использование рекурсивного алгоритма. Вот пример реализации на Python:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def find_lca(root, p, q):
    if root is None:
        return None
    if root == p or root == q:
        return root
    left_lca = find_lca(root.left, p, q)
    right_lca = find_lca(root.right, p, q)
    if left_lca and right_lca:
        return root
    if left_lca:
        return left_lca
    if right_lca:
        return right_lca
    return None

Метод 2. Использование родительских указателей.
Другой подход заключается в использовании родительских указателей при обходе дерева. Этот метод требует дополнительного места для хранения родительских указателей каждого узла. Вот пример реализации на Python:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
def populate_parent_pointers(root, parent=None):
    if root is None:
        return
    root.parent = parent
    populate_parent_pointers(root.left, root)
    populate_parent_pointers(root.right, root)
def find_lca_with_parent_pointers(p, q):
    ancestors = set()
    while p:
        ancestors.add(p)
        p = p.parent
    while q:
        if q in ancestors:
            return q
        q = q.parent
    return None

Метод 3: использование метода двоичного подъема
Двоичный подъем — это усовершенствованный метод, который оптимизирует вычисление LCA для нескольких запросов в дереве. Он предварительно обрабатывает дерево и сохраняет информацию, которая позволяет проводить эффективные расчеты LCA. Вот пример реализации на Python:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def preprocess_tree(root):
    MAX_N = 1000  # Maximum number of nodes in the tree
    MAX_LOGN = 10  # Maximum logarithmic depth of the tree
    parent = [[0] * MAX_LOGN for _ in range(MAX_N)]
    depth = [0] * MAX_N
    def dfs(node, par=None):
        parent[node][0] = par
        if par is not None:
            depth[node] = depth[par] + 1
        for child in [node.left, node.right]:
            if child:
                dfs(child, node)
    dfs(root)
    for j in range(1, MAX_LOGN):
        for i in range(MAX_N):
            if parent[i][j - 1] != -1:
                parent[i][j] = parent[parent[i][j - 1]][j - 1]
    return parent, depth
def find_lca_with_binary_lifting(p, q, parent, depth):
    MAX_LOGN = 10  # Maximum logarithmic depth of the tree
    if depth[p] < depth[q]:
        p, q = q, p
    for i in range(MAX_LOGN - 1, -1, -1):
        if depth[p] - (1 << i) >= depth[q]:
            p = parent[p][i]
    if p == q:
        return p
    for i in range(MAX_LOGN - 1, -1, -1):
        if parent[p][i] != parent[q][i]:
            p = parent[p][i]
            q = parent[q][i]
    return parent[p][0]

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