Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
Example:
Input: root = [4,2,5,1,3], target = 3.714286, and k = 2 4 / \ 2 5 / \ 1 3 Output: [4,3]
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
struct Solution;
use rustgym_util::*;
trait Inorder {
fn inorder(&self, values: &mut Vec<i32>);
}
impl Inorder for TreeLink {
fn inorder(&self, values: &mut Vec<i32>) {
if let Some(node) = self {
let node = node.borrow();
node.left.inorder(values);
values.push(node.val);
node.right.inorder(values);
}
}
}
impl Solution {
fn closest_k_values(root: TreeLink, target: f64, k: i32) -> Vec<i32> {
let mut values = vec![];
root.inorder(&mut values);
let n = values.len();
let k = k as usize;
let mut start = 0;
let mut end = n;
while end - start > k {
if (values[start] as f64 - target).abs() > (values[end - 1] as f64 - target).abs() {
start += 1;
} else {
end -= 1;
}
}
values[start..end].to_vec()
}
}
#[test]
fn test() {
let root = tree!(4, tree!(2, tree!(1), tree!(3)), tree!(5));
let target = 3.714286;
let k = 2;
let res = vec![3, 4];
assert_eq!(Solution::closest_k_values(root, target, k), res);
}