/* Наименьший общий предок в дереве за O(1) памяти Описание л Дано бинарное дерево (не поиска): struct Node { Node* parent; Node* left; Node* right; } Нужно написать функцию, которая для двух данных вершин будет возвращать их наименьшего (ближайшего) общего предка: Node* Lca (Node* a, Node* b); */

Для поиска наименьшего общего предка (LCA) в бинарном дереве с указателями на родителей и без дополнительной памяти можно использовать следующий подход:

1. Вычислить глубину каждой из двух вершин.
2. Поднять более глубокую вершину вверх по цепочке родителей, пока глубины не сравняются.
3. Затем одновременно подниматься вверх по родителям обеих вершин, пока они не совпадут — это и будет LCA.

Пример на Go:

type Node struct {
    parent *Node
    left   *Node
    right  *Node
}

func depth(n *Node) int {
    d := 0
    for n != nil {
        n = n.parent
        d++
    }
    return d
}

func Lca(a, b *Node) *Node {
    da := depth(a)
    db := depth(b)

    // Поднимаем более глубокий узел
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // Поднимаемся вместе, пока не найдём общий предок
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

Этот алгоритм использует только указатели и константную память, работает за время O(h), где h — высота дерева.