Ctrl K

Самая близкая пара в дереве поиска

Лёгкая
Дан корень root двоичного дерева поиска: для каждой вершины все значения в левом поддереве меньше её значения, а в правом — больше. Все значения различны. Верните наименьшую разницу между значениями двух разных вершин дерева.
Пример 1
root=tree_node([20, 10, 30, 5, 14, 25]) → 4

В порядке возрастания значения такие: 5, 10, 14, 20, 25, 30. Разницы соседей: 5, 4, 6, 5, 5, наименьшая из них 4 — между 10 и 14.

Пример 2
root=tree_node([50, None, 51]) → 1

Всего две вершины, их разница 1.

Ограничения
  • Число вершин в дереве от 2 до 5 · 10⁴
  • 0 ≤ Node.val ≤ 10⁵
  • Дерево является корректным деревом поиска
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПара в дереве поиска ЛёгкаяДеревья-близнецы ЛёгкаяДерево-зеркало ЛёгкаяВысота дерева ЛёгкаяГлубина ближайшего листа Лёгкая
загружаем Python…
Вход
root=tree_node([20, 10, 30, 5, 14, 25])
Ожидается
4

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 52 теста на сервере, включая скрытые.