Середина
Проблема
Для заданного бинарного дерева найдите наименьшего общего предка (LCA) двух заданных узлов в дереве.
Согласно определению LCA в Википедии: «Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в T, у которого есть потомки p и q (где мы допускаем узел быть потомок самого себя).
Для следующего бинарного дерева: root = [3,5,1,6,2,0,8,null,null,7,4]
______3.
_____
/ \
__4
_ __5
_
/ \ / \
6 _2 0 8
/ \
7 4
Пример 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of of nodes5
and1
is3.
Пример 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes5
and4
is5
, since a node can be a descendant of itself according to the LCA definition.
Примечание.
- Все значения узлов будут уникальными.
- p и q различны, и оба значения будут существовать в двоичном дереве.
Решение
Как и #235, мы можем проверить root
с помощью p
и q
, чтобы определить, является ли root
LCA или нет. Разница в том, что мы должны выполнять рекурсивную проверку, чтобы узнать, находятся ли p
и q
в поддеревьях текущего корня или нет.
Сложность
Очевидно, что мы обходим каждый узел один раз, поэтому это займет O(n) время, где n
означает количество узлов в этом дереве.
Из-за пространственной сложности, поскольку каждый узел проходится один раз с O(1) дополнительным пространством для каждой рекурсии, также требуется O(n) дополнительного пространства.
Следовать за
Если есть большие запросы на поиск LCA в одном дереве, подход RMQ может решить проблему on-line LCA за O(n + qlogn) и подход Тарьяна может решить LCA в автономном режиме за O(n + q), где n
и q
обозначают количество узлов в этом дереве и количество запросов соответственно.