7. Lowest Common Ancestor

«Простота — необходимое условие надежности».
— Эдсгер Вибе Дейкстра

LeetCode 236. Lowest Common Ancestor of a Binary Tree. Дано бинарное дерево и два различных узла $p$ и $q$, гарантированно присутствующие в нём. Требуется найти их наименьшего общего предка (Lowest Common Ancestor, LCA) — наиболее глубокий узел в дереве, для которого как $p$, так и $q$ являются потомками (при этом узел считается потомком самого себя).

После решения задачи о максимальной сумме пути (6. Binary Tree Maximum Path Sum) мы продолжаем исследовать мощь обратного обхода (Postorder DFS). Но если в предыдущей задаче мы передавали снизу вверх числовые суммы, то в задаче о наименьшем общем предке наверх транслируются топологические маркеры обнаружения.

Для Senior Go-разработчика эта задача — эталон чистоты рекурсивного мышления: элегантный код в 12 строк без вспомогательных структур данных и без единой аллокации в куче заменяет громоздкие решения с сохранением путей и родительских указателей.

1. Архитектурная идея: восходящий сбор сигналов

Вместо того чтобы строить пути от корня к узлам $p$ и $q$ и затем искать их расхождение, мы используем естественную топологию дерева. Запустим рекурсию в поддеревья и сформулируем строгий контракт функции:

Инвариант lowestCommonAncestor(node, p, q):

1. Если в поддереве node нет ни $p$, ни $q$ $\rightarrow$ возвращает nil.
2. Если в поддереве node найден ровно один из искомых узлов $\rightarrow$ возвращает указатель на этот узел ($p$ или $q$).
3. Если в поддереве node найдены оба узла $\rightarrow$ возвращает их наименьшего общего предка.

              Случай 1: Разделение ветвей               Случай 2: Один предок другого
                       [ Node (LCA) ]                                [ p (LCA) ]
                       /            \                                     \
                   ...                ...                                 ...
                   /                    \                                   \
                 [p]                    [q]                                 [q]
          left != nil && right != nil                      left == nil, right == q (или наоборот)
           -> Node и есть ответ!                            -> p возвращается сразу наверх!

Почему корректно не спускаться глубже при node == p || node == q?

Если мы дошли до узла p, мы сразу возвращаем p родителю, даже не заглядывая в его детей. Почему?

• Если $q$ лежит в поддереве $p$: по определению, узел является предком самого себя, значит $p$ и есть искомый LCA! Нам не нужно искать $q$ внутри.
• Если $q$ лежит в другой ветке дерева: рекурсивный поиск в другой ветке найдет $q$, а их общий предок выше объединит результаты left != nil && right != nil и вернет истинный LCA.

2. Вопросы интервьюеру перед реализацией

• Гарантируется ли наличие обоих узлов в дереве?
  Ответ: В стандартной задаче LeetCode 236 — да, $p$ и $q$ всегда присутствуют и $p \neq q$. (Если узлы не гарантированы — см. раздел «Собеседование» ниже).
• Могут ли узлы дублироваться по значению?
  Ответ: Все значения узлов уникальны, однако наш алгоритм сравнивает указатели на узлы, а не их значения, поэтому он инвариантен к значениям.
• Разрешено ли мутировать узлы дерева (добавлять указатель на родителя)?
  Ответ: Нет, дерево неизменяемо (read-only).

3. Идиоматическая реализация на Go

package main

// TreeNode представляет узел бинарного дерева.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// lowestCommonAncestor находит наименьшего общего предка для узлов p и q.
// Временная сложность: O(N) в худшем случае (посещаем каждый узел один раз).
// Пространственная сложность: O(H) — глубина рекурсивного стека, где H — высота дерева.
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // Базовый случай: пустое дерево или один из искомых узлов найден.
    if root == nil || root == p || root == q {
        return root
    }

    // Пост-обход (Postorder): сначала ищем в поддеревьях.
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    // Развилка: если оба вызова вернули не-nil, то p и q находятся
    // в разных поддеревьях относительно текущего root. Значит, root — их LCA!
    if left != nil && right != nil {
        return root
    }

    // Если один из вызовов вернул результат (а второй nil),
    // пробрасываем найденный узел (или уже найденный LCA) выше по стеку.
    if left != nil {
        return left
    }
    return right
}

4. Визуализация логики принятия решений

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc

    Start["Вход: LCA(root, p, q)"]:::entry --> BaseCheck{"root == nil<br>|| root == p<br>|| root == q?"}:::warning

    BaseCheck -- "Да" --> ReturnRoot["return root"]:::accent
    BaseCheck -- "Нет" --> SearchChildren["left = LCA(root.Left, p, q)<br>right = LCA(root.Right, p, q)"]:::process

    SearchChildren --> CheckBoth{"left != nil<br>&& right != nil?"}:::warning

    CheckBoth -- "Да: развилка обнаружена" --> FoundLCA["return root // текущий узел и есть LCA"]:::success
    CheckBoth -- "Нет" --> CheckLeft{"left != nil?"}:::warning

    CheckLeft -- "Да" --> ReturnLeft["return left"]:::process
    CheckLeft -- "Нет" --> ReturnRight["return right"]:::process
  

5. Сравнение подходов: Рекурсивный DFS vs Родительский словарь

В варианте с хеш-таблицей родителей (parentMap := make(map[*TreeNode]*TreeNode)) приходится заполнять словарь на $N$ элементов, а затем строить visited := make(map[*TreeNode]bool) для подъёма от $p$ к корню. Это порождает паразитное выделение памяти в куче и нагружает GC. Рекурсивное решение работает исключительно на стеке горутины.

6. Механическая симпатия Go: указатели и регистры ABI

1. Регистровый ABI (Go 1.17+):
   Параметры root, p, q — это три 64-битных указателя (*TreeNode). Они передаются напрямую через регистры CPU (например, RAX, RBX, RCX на amd64), исключая обращения к памяти для передачи аргументов функции.
2. Сравнение указателей в железе:
   Проверка root == p компилируется в одну ассемблерную инструкцию CMPQ reg1, reg2. Это мгновенное сравнение двух целочисленных адресов памяти без разыменования указателей.
3. Отсутствие Escape Analysis:
   Поскольку функция оперирует исключительно адресами существующих узлов и не создаёт новых переменных в куче, рантайм Go выполняет её со стоимостью 0 B/op.

7. Граничные случаи (Edge Cases)

• $p$ является прямым родителем $q$:
  Алгоритм встретит $p$, сработает базовый случай root == p, и $p$ немедленно вернется наверх. Правая/левая ветки под $p$ даже не будут обходиться. Ответ $p$ корректен.
• Узлы находятся в противоположных концах дерева:
  Корень увидит left != nil из одного дальнего листа и right != nil из другого дальнего листа. Результат root вернется на самом верху дерева.
• Вырожденное дерево-список глубины $N$:
  Стек горутины плавно вырастет до необходимого размера за счет динамического реаллоцирования страниц стека (runtime.morestack).

Резюме для интервью

В следующей задаче — 8. Flood Fill — мы завершим кластер DFS, перейдя от древовидных структур к матрицам и алгоритмам растровой заливки.