Середина

Проблема

Для заданного бинарного дерева найдите наименьшего общего предка (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 nodes 5 and 1 is 3.

Пример 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, 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 обозначают количество узлов в этом дереве и количество запросов соответственно.