Наименьший общий предок

O(n)

Рекурсия, в которой каждый вызов сообщает наверх, нашёл ли он один из двух искомых узлов ниже себя, и узел, где эти сообщения впервые сходятся вместе, и есть точка разделения.

Сигналы

наименьший общий предок двух узловсамый глубокий узел, который является предком и p, и qкаждый рекурсивный вызов возвращает, какой из целевых узлов найден под нимпуть от корня до каждого узла и их сравнение (альтернативный подход)дано бинарное дерево или BST, найти точку, где расходятся два пути

Шаблон

function lca(node, p, q) {
    if (!node || node === p || node === q) return node;
    const left = lca(node.left, p, q);
    const right = lca(node.right, p, q);
    if (left && right) return node; // p and q split here
    return left || right;
}

Похоже, но не то

Обход дерева: Обычный обход просто посещает каждый узел по порядку и не передаёт наверх информацию о том, что нашёл. LCA это конкретная рекурсия, возвращаемое значение которой сообщает, найдены ли p, q или оба в поддереве, поэтому точка слияния распознаётся за один проход.

n узлов, один проход -> O(n) времени: каждый узел сообщает родителю, найдены ли под ним p, q или оба, и точка разделения проявляется после посещения каждого узла один раз.

Изучить этот паттерн