270. Closest Binary Search Tree Value

public class Solution {
    public int ClosestValue(TreeNode root, double target) {
        int closest = root.val;
        while (root != null) {
            if (Math.Abs(root.val - target) < Math.Abs(closest - target)) {
                closest = root.val;
            } else if (Math.Abs(root.val - target) == Math.Abs(closest - target)) {
                closest = Math.Min(root.val, closest);
            }
            root = target < root.val ? root.left : root.right;
        }
        return closest;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ClosestValue(TreeNode root, double target) {
        int closest = root.val;
        while (root != null) {
            if (abs(root.val - target) < abs(closest - target)) {
                closest = root.val;
            } else if (abs(root.val - target) == abs(closest - target)) {
                closest = min(root.val, closest);
            }
            root = target < root.val ? root.left : root.right;
        }
        return closest;
    }
}

class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        while (root != null) {
            if (Math.abs(root.val - target) < Math.abs(closest - target)) {
                closest = root.val;
            } else if (Math.abs(root.val - target) == Math.abs(closest - target)) {
                closest = Math.min(root.val, closest);
            }
            root = target < root.val ? root.left : root.right;
        }
        return closest;
    }
}

var closestValue = function(root, target) {
    let closest = root.val;
    while (root) {
        if (Math.abs(root.val - target) < Math.abs(closest - target)) {
            closest = root.val;
        } else if (Math.abs(root.val - target) === Math.abs(closest - target)) {
            closest = Math.min(root.val, closest);
        }
        root = target < root.val ? root.left : root.right;
    }
    return closest;
};

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

package main

import "math"

func closestValue(root *TreeNode, target float64) int {
    closest := root.Val
    for root != nil {
        if math.Abs(float64(root.Val)-target) < math.Abs(float64(closest)-target) {
            closest = root.Val
        } else if math.Abs(float64(root.Val)-target) == math.Abs(float64(closest)-target) {
            if root.Val < closest {
                closest = root.Val
            }
        }
        if target < float64(root.Val) {
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return closest
}

Algorithm

1️⃣

Построить массив с помощью inorder обхода:

Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2️⃣

Найти ближайший элемент:

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

3️⃣

Выбрать наименьший из ближайших элементов:

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

😎