Задача: 270. Closest Binary Search Tree Value
Сложность: easy

Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.

Пример:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

👨‍💻 Алгоритм:

1⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.

3⃣Выбрать наименьший из ближайших элементов:
Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них.

😎 Решение:

class Solution {
    func closestValue(_ root: TreeNode?, _ target: Double) -> Int {
        var closest = root!.val
        var node = root
        while node != nil {
            if abs(Double(node!.val) - target) < abs(Double(closest) - target) {
                closest = node!.val
            } else if abs(Double(node!.val) - target) == abs(Double(closest) - target) {
                closest = min(node!.val, closest)
            }
            node = target < Double(node!.val) ? node!.left : node!.right
        }
        return closest
    }
}

Ставь 👍 и забирай 📚 Базу знаний