Соседи снизу и сверху в дереве поиска

Средняя

Дан корень root двоичного дерева поиска (все значения в левом поддереве вершины меньше её значения, в правом — больше) и массив чисел probes. Для каждого числа x из probes найдите пару [lo, hi]: - lo — наибольшее значение в дереве, не превосходящее x, или -1, если такого нет; - hi — наименьшее значение в дереве, не меньшее x, или -1, если такого нет. Верните список пар в порядке чисел в probes.

Пример 1

root=tree_node([20, 10, 35, 5, 15, None, 50]), probes=[15, 27, 3, 60] → [[15, 15], [20, 35], [-1, 5], [50, -1]]

15 есть в дереве, поэтому [15, 15]. Для 27 ближайшее снизу — 20, сверху — 35. Меньше 3 в дереве ничего нет, а ближайшее сверху — 5. Для 60 сверху ничего нет.

Пример 2

root=tree_node([7, None, 12]), probes=[9] → [[7, 12]]

9 лежит между 7 и 12.

Ограничения

2 ≤ число вершин ≤ 10⁵
1 ≤ Node.val ≤ 10⁶
Дерево — корректное дерево поиска с различными значениями
1 ≤ len(probes) ≤ 10⁵
1 ≤ probes[i] ≤ 10⁶

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Tree Depth-First Search Binary Search Tree Array Binary Search Binary Tree

Вход

root=tree_node([20, 10, 35, 5, 15, None, 50]), probes=[15, 27, 3, 60]

Ожидается

[[15, 15], [20, 35], [-1, 5], [50, -1]]

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