2022-11-22 18:59:27
Найти ближайшее значение в бинарном дереве
Напишите функцию, которая принимает два аргумента — бинарное дерево и значение в виде числа, а возвращает ближайшее значение, найденное в бинарном дереве.
Node = { value: number | null, left: Node | null, right: Node | null }
Решение доступно на картинке. Зная свойство сбалансированного бинарного дерева, где слева находятся все значения нод меньше текущей, а справа равные или больше по значению, мы можем в лучшем случае откидывать каждый раз половину дерева.
В данном решении мы идем рекурсивным путём по нодам, записывая и сравнивая разницу со значением из аргумента. Если значение равно нужному, значит мы нашли нужную нам ноду, а иначе мы смотрим, является ли текущее значение ноды меньше или больше того, которое мы ищем. В зависимости от этого мы продолжаем рекурсивно спускаться в нужном нам направлении, обновляя разницу, до тех пор пока не упремся в конец ветки.
1.0K views15:59