二叉搜索树中最接近的值 II
题目:二叉搜索树中最接近的值 II
给定一棵非空二叉搜索树以及一个target值,找到 BST 中最接近给定值的 k
个数。
示例:
输入:
{3,1,4,#,2}
0.275000
2
输出:
[1,2]
解释:
二叉树 {3,1,4,#,2},表示如下的树结构:
3
/ \
1 4
\
2
题解:二分法+双指针
1. 分治法将二叉树所有节点存储在集合中
2.二分法找到target在集合中应该插入的下标
3.从插入的下标开始,利用双指针依次找到最接近的k个值。
public class Solution {
List<Integer> list;
public void preOrder(TreeNode root) {
if (root == null) return;
preOrder(root.left);
list.add(root.val);
preOrder(root.right);
}
public List<Integer> closestKValues(TreeNode root, double target, int k) {
list = new ArrayList<>();
List<Integer> res = new ArrayList<>();
preOrder(root);
int length = list.size();
//求得插入点
int mid = 0, left = 0, right = length - 1;
while (left < right) {
mid = (left + right) / 2;
if (target < list.get(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
left = mid;
right = mid + 1;
int index = 0;
//双指针求最接近的k个值
while (left >= 0 && right < length && index < k) {
double leftDValue = Math.abs(target - list.get(left));
double rightDValue = Math.abs(target - list.get(right));
if (leftDValue < rightDValue) {
res.add(list.get(left));
left--;
index++;
} else {
res.add(list.get(right));
right++;
index++;
}
}
if (index < k) {
if (left >= 0) {
while (left >= 0 && index < k) {
res.add(list.get(left));
left--;
index++;
}
} else {
while (right < length && index < k) {
res.add(list.get(right));
right++;
index++;
}
}
}
return res;
}
}