272. Closest Binary Search Tree Value II

leetcode hard

#array#csharp#graph#hard#leetcode#math#search#sort#tree#two-pointers

Task

Дано корень бинарного дерева поиска, целевое значение и целое число k. Верните k значений в дереве, которые ближе всего к целевому значению. Вы можете вернуть ответ в любом порядке.

Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.

Пример:

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

Output: [4,3]

C# solution

matched/original

public class Solution {
    public IList<int> ClosestKValues(TreeNode root, double target, int k) {
        var arr = new List<int>();
        Dfs(root, arr);
        arr.Sort((o1, o2) => Math.Abs(o1 - target).CompareTo(Math.Abs(o2 - target)));
        return arr.Take(k).ToList();
    }
    private void Dfs(TreeNode node, List<int> arr) {
        if (node == null) return;
        arr.Add(node.val);
        Dfs(node.left, arr);
        Dfs(node.right, arr);
    }
}

C++ solution

auto-draft, review before submit

#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 vector<int> ClosestKValues(TreeNode root, double target, int k) {
        var arr = new List<int>();
        Dfs(root, arr);
        arr.Sort((o1, o2) => abs(o1 - target).CompareTo(abs(o2 - target)));
        return arr.Take(k).ToList();
    }
    private void Dfs(TreeNode node, List<int> arr) {
        if (node == null) return;
        arr.push_back(node.val);
        Dfs(node.left, arr);
        Dfs(node.right, arr);
    }
}

Java solution

matched/original

class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> arr = new ArrayList<>();
        dfs(root, arr);
        arr.sort((o1, o2) -> Math.abs(o1 - target) <= Math.abs(o2 - target) ? -1 : 1);
        return arr.subList(0, k);
    }
    
    private void dfs(TreeNode node, List<Integer> arr) {
        if (node == null) {
            return;
        }
        arr.add(node.val);
        dfs(node.left, arr);
        dfs(node.right, arr);
    }
}

JavaScript solution

matched/original

var closestKValues = function(root, target, k) {
    const arr = [];
    dfs(root, arr);
    arr.sort((o1, o2) => Math.abs(o1 - target) - Math.abs(o2 - target));
    return arr.slice(0, k);
};

function dfs(node, arr) {
    if (!node) return;
    arr.push(node.val);
    dfs(node.left, arr);
    dfs(node.right, arr);
}

Python solution

matched/original

class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        arr = []
        self.dfs(root, arr)
        arr.sort(key=lambda x: abs(x - target))
        return arr[:k]
    
    def dfs(self, node: TreeNode, arr: List[int]):
        if not node:
            return
        arr.append(node.val)
        self.dfs(node.left, arr)
        self.dfs(node.right, arr)

Go solution

matched/original

import (
    "math"
    "sort"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func closestKValues(root *TreeNode, target float64, k int) []int {
    var arr []int
    dfs(root, &arr)
    sort.Slice(arr, func(i, j int) bool {
        return math.Abs(float64(arr[i])-target) < math.Abs(float64(arr[j])-target)
    })
    return arr[:k]
}

func dfs(node *TreeNode, arr *[]int) {
    if node == nil {
        return
    }
    *arr = append(*arr, node.Val)
    dfs(node.Left, arr)
    dfs(node.Right, arr)
}

Explanation

Algorithm

1️⃣

Выполнить обход дерева в глубину (DFS) и собрать все значения в массив:

Пройти по дереву в глубину, добавляя каждое значение узла в массив.

2️⃣

Отсортировать массив по расстоянию от целевого значения:

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

3️⃣

Вернуть первые k значений из отсортированного массива:

Извлечь первые k элементов из отсортированного массива и вернуть их.

😎