Сложность: easy
Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286
Output: 4
👨💻 Алгоритм:
1️⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.
2️⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.
3️⃣Выбрать наименьший из ближайших элементов:
Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них.
😎 Решение:
class Solution:
def closestValue(self, root: TreeNode, target: float) -> int:
closest = root.val
while root:
closest = min(root.val, closest, key=lambda x: (abs(target - x), x))
root = root.left if target < root.val else root.right
return closest
Ставь 👍 и забирай 📚 Базу знаний