План курса / Все задачи / Алгоритмы и структуры данных
Поиск ближайшего значения
средне
Дан корень бинарного дерева поиска (BST) и значение target. Нужно вернуть наиболее близкое значение узла дерева к target. Если таких значений несколько, то нужно вернуть наименьшее
ВАЖНО: реализуй обход без использования рекурсии
Пример 1:
Ввод: root = [10,5,11,-2,7,null,15], target = 6.0
Вывод: 5
Объяснение: наиболее близкие значения к 6 это 5 и 7, но возвращаем 5 т к при равной удаленности значений выбираем наименьшее
Пример 2:
Ввод: root = [10,5,11,-2,7,null,15], target = 5.4
Вывод: 5
Объяснение: наиболее близкое значение в дереве к target = 5.4 это 5
Ограничения:
Число узлов в дереве >= 1
Высота дерева <= 1000
/**
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution
{
private static int MostCloseValue(int a, int b, double target)
{
// находим наиболее близкое значение к target
if (Math.Abs(target - a) < Math.Abs(target - b))
{
return a;
}
else if (Math.Abs(target - a) == Math.Abs(target - b))
{
return Math.Min(a, b);
}
return b;
}
public static int ClosestBstValue(TreeNode root, double target)
{
int closest = root.val;
while (root != null)
{
closest = MostCloseValue(root.val, closest, target);
// обходим только одно поддерево, где могут быть наиболее близкие значения
if (root.val > target)
{
root = root.left;
}
else
{
root = root.right;
}
}
return closest;
}
}
#include <vector>
using namespace std;
/**
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
int mostCloseValue(int a, int b, double target) {
// находим наиболее близкое значение к target
if (abs(target - a) < abs(target - b)) {
return a;
} else if (abs(target - a) == abs(target - b)) {
return min(a, b);
}
return b;
}
int closestBstValue(TreeNode* root, double target) {
int closest = root->val;
while (root != nullptr) {
closest = mostCloseValue(root->val, closest, target);
// обходим только одно поддерево, где могут быть наиболее близкие значения
if (root->val > target) {
root = root->left;
} else {
root = root->right;
}
}
return closest;
}
package main
import "math"
// type TreeNode struct {
// Val int
// Left *TreeNode
// Right *TreeNode
// }
func mostCloseValue(a, b int, target float64) int {
// находим наиболее близкое значение к target
if math.Abs(target-float64(a)) < math.Abs(target-float64(b)) {
return a
} else if math.Abs(target-float64(a)) == math.Abs(target-float64(b)) {
return min(a, b)
}
return b
}
func closestBstValue(root *TreeNode, target float64) int {
closest := root.Val
for root != nil {
closest = mostCloseValue(root.Val, closest, target)
// обходим только одно поддерево, где могут быть наиболее близкие значения
if float64(root.Val) > target {
root = root.Left
} else {
root = root.Right
}
}
return closest
}
import java.util.*;
/**
* class TreeNode {
* Integer val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(Integer val) { this.val = val; }
* TreeNode(Integer val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int mostCloseValue(int a, int b, double target) {
// находим наиболее близкое значение к target
if (Math.abs(target - a) < Math.abs(target - b)) {
return a;
} else if (Math.abs(target - a) == Math.abs(target - b)) {
return Math.min(a, b);
}
return b;
}
public int closestBstValue(TreeNode root, double target) {
int closest = root.val;
while (root != null) {
closest = mostCloseValue(root.val, closest, target);
// обходим только одно поддерево, где могут быть наиболее близкие значения
if (root.val > target) {
root = root.left;
} else {
root = root.right;
}
}
return closest;
}
}
from tree_node import TreeNode
# class TreeNode:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def most_close_value(a: int, b: int, target: float) -> int:
# находим наиболее близкое значение к target
if abs(target - a) < abs(target - b):
return a
elif abs(target - a) == abs(target - b):
return min(a, b)
return b
def closest_bst_value(root: TreeNode, target: float) -> int:
closest = root.val
while root:
closest = most_close_value(root.val, closest, target)
# обходим только одно поддерево, где могут быть наиболее близкие значения
if root.val > target:
root = root.left
else:
root = root.right
return closest
/*
class TreeNode {
constructor(value) {
this.val = value;
this.left = null;
this.right = null;
}
}
*/
export function mostCloseValue(a, b, target) {
// находим наиболее близкое значение к target
if (Math.abs(target - a) < Math.abs(target - b)) {
return a;
} else if (Math.abs(target - a) === Math.abs(target - b)) {
return Math.min(a, b);
}
return b;
}
/**
* @param {TreeNode|null} root
* @param {number} target
* @returns {number}
*/
export function closestBstValue(root, target) {
let closest = root.val;
while (root !== null) {
closest = mostCloseValue(root.val, closest, target);
// обходим только одно поддерево, где могут быть наиболее близкие значения
if (root.val > target) {
root = root.left;
} else {
root = root.right;
}
}
return closest;
}