Minimum Absolute Difference in BST

Лёгкая№530симметричный

Дан корень двоичного дерева поиска, в нём не меньше двух узлов. Нужно вернуть наименьшую разницу между значениями любых двух узлов. Наше дерево: 20 с потомками 9 и 31; у 9 потомки 4 и 15; у 31 только левый потомок 24 — ответ 4, между 24 и 20.

530 Minimum Absolute Difference in BSTРазбор · 1×

Пример: наименьшая разница между двумя значениями двоичного дерева поиска: обходим его по возрастанию и сравниваем каждое значение с предыдущим.

nonenonenonenonenonenonenone2093141524по порядку—стек вызововвершина справа—
ещё не посещёнждёт в стеке вызововтекущий вызовprev, сравниваем с узломего значение уже позадиnone: пустой потомок

prev = none: пока ни одного значения

01/46
сначала · назад · пуск · шаг
Скорость
1function getMinimumDifference(root):
2 prev = none // shared by every call of inorder
3 best = infinity
4 inorder(root)
5 return best
6
7function inorder(node):
8 if node is none:
9 return
10 inorder(node.left)
11 if prev is not none:
12 best = min(best, node.val - prev)
13 prev = node.val
14 inorder(node.right)
состояние
node
–
prev
–
best
–
нажмите шаг, чтобы вернуться

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

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

  1. В двоичном дереве поиска симметричный обход проходит значения по возрастанию, поэтому prev — всегда наибольшее значение меньше узла.
  2. В отсортированном списке ближе всех всегда два соседа: всё, что дальше, отличается не меньше. Поэтому n − 1 сравнений с prev покрывают все пары, которые могут победить.
  3. Сосед по возрастанию часто не родитель: рядом с 24 стоит корень 20 двумя уровнями выше.

Сложность

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

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

Решить на LeetCode ↗

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