二叉搜索树中最接近的值 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;     } }

推荐这些技术文章：

Python笔试题：小力将 N 个零件的报价存于数组 nums。小力预算为 target，假定小力仅购买两个零件，要求购买零件的花费不超过预算，请问他有多少种采购方案。【杭州多测师】【杭州多测师_王sir】

def test1(nums, target):
nums.sort() #先排序
left,right = 0,len(nums)-1
n = 0
while(left < right):
if(nums[left] + nums[right] > target):
right...

【LeetCode】剑指 Offer II 006. 排序数组中两个数字之和

class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int length=numbers.size();
int left,right,cpl=length-1,m;
int flag=0;
vector<in...

450. 删除二叉搜索树中的节点

递归
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {

if (root == null){
return root;
}

/**
* 如果大于当前节点，就在左子树寻找；小于则在右子树寻找
...

230. 二叉搜索树中第K小的元素

中序遍历
class Solution {
public int kthSmallest(TreeNode root, int k) {

ArrayList<Integer> list = new ArrayList<>();
inorder(root, list);

return list.get(k - 1)...

二分查找等于target、第一个小于等于target、第一个大于等于target的值

1 class Solution {
2 public:
3 // 查找第一个小于等于target的值
4 int binarySearch1(vector<int> vec, int target) {
5 int left = 0;
6 int right = vec.size() - 1;
7 wh...

34. 在排序数组中查找元素的第一个和最后一个位置

二分查找
class Solution {
public int[] searchRange(int[] nums, int target) {

/**
* 先找到任意一个target，记录位置
*/
int left = 0;
int right = nums.length - 1;
...

leetcode 669. 修剪二叉搜索树

递归：
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root==null) return root;
if(root.val<low) return trimBST(root.right,low,high);
else...

34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

 
示例...

二分查找/搜索使用方法

难点：
  二分查找的难点在于细节，不等号是否应该带等号
  如mid加一还是减一，while到底用<=还是<;
常用使用场景：寻找一个数，寻找左侧边界，寻找右侧边界
0.二分查找框架
注意点：
1. 不要出现else,把所有的情况用else if写清楚
2.  “...”标记的地方，是可能出现细节的地方，也是出现坑的地方
3. 为防止left和righ...

lc35. 搜索插入位置

''' 二分查找，末端边界比较明显，需要额外处理 '''class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if len(nums) == 0:
return 0
left = 0
right = len(n...