Ближайшее значение в дереве поиска

Лёгкая

Склад хранит номера ячеек в двоичном дереве поиска: в левом поддереве каждой вершины только меньшие номера, в правом — только большие. Дан корень root и число goal (оно может быть дробным). Верните номер ячейки из дерева, который ближе всего к goal. Если таких номеров два (один меньше goal, другой больше на то же расстояние), верните меньший. Обход всего дерева работает, но попробуйте воспользоваться его упорядоченностью и пройти только один путь от корня.

Пример 1

root=tree_node([20, 9, 31, 4, 15]), goal=17.4 → 15

Ближе всех к 17.4 значение 15: до него 2.4, а до 20 — 2.6.

Пример 2

root=tree_node([20, 9, 31, 4, 15]), goal=25.5 → 20

20 и 31 отстоят от 25.5 на 5.5 и 5.5 — ничья, берём меньшее, 20.

Пример 3

root=tree_node([7]), goal=-3.0 → 7

Ограничения

Число вершин от 1 до 10⁴
0 ≤ Node.val ≤ 10⁹, значения различны
Дерево — корректное дерево поиска
-10⁹ ≤ goal ≤ 10⁹

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

Решили0

Пробовали0

Отправок0

Принято—

Темы

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

Вход

root=tree_node([20, 9, 31, 4, 15]), goal=17.4

Ожидается

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