Где применяется
1. Задача
Два человека работают в одной компании. Тебе нужен их ближайший общий руководитель: тот тимлид или директор, у которого оба где-то в подчинении, и ниже которого такого человека нет. Поднимайся по цепочке начальников от каждого из двоих. Ответ это первое место, где два пути встречаются.
Такая же задача возникает на любом дереве. Даны два файла, и нужна самая глубокая папка, в которой лежат оба. Даны две категории в каталоге товаров, и нужна самая узкая группа, в которую входят обе. Даны два коммита, и нужна точка в истории, где они разошлись от общего предка.
Этот самый глубокий общий предок называют наименьшим общим предком (LCA, lowest common ancestor). Узел считается предком самого себя. Поэтому если один из двух узлов стоит прямо над другим, ответ это верхний узел.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитlca(root, 6, 4) // root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]Ищем наименьшего общего предка p = 6 и q = 4. Каждый вызов задаёт один вопрос: есть ли цель в моём поддереве?
Как узнать
Эти слова в условии значат этот паттерн
- наименьший общий предок двух узлов
- самый глубокий узел, который является предком и p, и q
- каждый рекурсивный вызов возвращает, какой из целевых узлов найден под ним
- путь от корня до каждого узла и их сравнение (альтернативный подход)
- дано бинарное дерево или BST, найти точку, где расходятся два пути
Похоже, но не то
- Двоичное дерево поиска (Binary search tree)
В дереве поиска направление задают сами значения. В обычном дереве надо спросить оба поддерева.
- Обход дерева (Tree traversal)
Та страница про три порядка посещения. Здесь обратный обход отвечает на один вопрос.
- Система непересекающихся множеств (Union-find (disjoint set))
Офлайновый алгоритм Тарьяна отвечает на много пар через непересекающиеся множества. Одной паре это не нужно.
- DP на деревьях (DP on trees)
Динамика на деревьях поднимает наверх посчитанные значения. Здесь наверх идёт только найдено или нет.
n узлов дают O(n) на один запрос. Для многих запросов берут двоичные подъёмы по O(log n).
На LeetCode
Задачи о том, где встречаются два узла дерева или какой путь между ними. Один обход post-order возвращает то, что нашла каждая сторона, и узел, где ответили обе стороны, и есть ответ.
Задача урока под тем же именем.
В дереве поиска сторону решают значения, так что иди влево, пока оба меньше, вправо, пока оба больше, и остановись там, где они расходятся.
Возвращай вместе с узлом глубину, и когда обе стороны одинаково глубокие, ответом будет текущий узел.
Найди путь от корня до каждого узла, отрежь общее начало, оно кончается на LCA, а первый путь замени на ходы U.