Lowest Common Ancestor of a Binary Tree

Средняя№236узлы дерева

Дан корень двоичного дерева и два разных его узла, p и q. Нужно найти их наименьшего общего предка — самый глубокий узел, в поддереве которого есть и p, и q; узел считается частью своего же поддерева. Наше дерево: 5 с потомками 8 и 2; у 8 потомки 4 и 1; у 1 левый потомок 7; у 2 правый потомок 9. p = 4, q = 7 — ответ 8.

236 Lowest Common Ancestor of a Binary TreeРазбор · 1×

Пример: найти самый низкий узел, под которым есть и 4, и 7: каждый вызов возвращает p или q, если нашёл, а первый узел, которому ответили обе стороны, — ответ.

p = 4, q = 7nonenonenonenonenonenonenonenone5824179стек вызововвершина справа5
не посещёнp или q, ещё не дошлиждёт в стеке вызововтекущий вызоввернул узел, ↑ какойвернул none: ниже нет ни p, ни q

5 — не none, и это ни p, ни q: ищем в обоих его поддеревьях

01/47
сначала · назад · пуск · шаг
Скорость
1function lca(node, p, q):
2 if node is none or node == p or node == q:
3 return node
4 left = lca(node.left, p, q)
5 right = lca(node.right, p, q)
6 if left is not none and right is not none:
7 return node // p and q split here
8 if left is not none:
9 return left
10 return right
состояние
p
4
q
7
node
5
left
–
right
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Вызов возвращает none ровно тогда, когда в его поддереве нет ни p, ни q, поэтому в каждом узле left и right говорят, с какой стороны они лежат.
  2. Если что-то нашлось с обеих сторон, p и q разошлись по разным поддеревьям, и ни один узел ниже не держит обоих: этот узел — самый низкий. Каждый вызов выше получает ответ только с одной стороны и просто передаёт его наверх.
  3. Если бы p лежал выше q, вызов на p сразу вернул бы p, не заглядывая ниже, и это верно: q где-то под p, значит, ответ — p.

Сложность

Время O(n): каждый узел посещаем не больше одного раза. Память O(h), где h — высота дерева: в стеке вызовов лежит один путь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.