在二叉搜索树中找到与目标数字最接近的 k 个数字
Finding the k closest numbers to a target number in a binary search tree
我遇到了下面的 leetcode 问题，我对一些人用来解决它的方法有疑问。问题是：
给定一棵非空二叉搜索树和一个目标值，在BST中找到k个最接近目标的值。
注意：
给定的目标值是一个浮点数。
您可以假设 k 始终有效，即：k ≤ 总节点数。
您保证在 BST 中只有一组唯一的 k 值最接近目标。
所以，有些人所做的是，他们进行了有序遍历，同时维护了一个大小为 k 的最近元素队列。在顺序遍历期间，如果他们发现一个元素比队列中的第一个节点更接近目标，他们从队列中删除第一个节点并添加当前值。我的问题是，为什么他们与队列中的第一个元素进行比较？这是我所指的一些代码：
https://leetcode.com/discuss/94472/inorder-one-linkedlist-java-solution-beat-85%25
据推测，队列中的第一个节点距离队列中元素的目标最远，只有在找到比它更近的节点时才需要更改队列。
中序遍历会先找到所有小于等于目标的元素。随着它的接近，新的、越来越近的元素将按排序顺序添加到列表的尾部。当它达到长度 k 后，在尾部添加一个新的更近的元素需要删除一个更远的元素。最远的是头部，所以它删除了。
搜索通过目标后，它开始看到距离目标越来越远的元素。每个人考虑的问题是它是否比列表中的目标更接近目标。假设 k=5 列表如下所示：
a <= b <= c <= d <= e (<= x?)
^
Target value somewhere between c and d
而下一个值 x >= e 刚刚被搜索发现。只有两种可能：
x比a更接近目标。在这种情况下，我们要删除 a 并在尾部添加 x。
x比a离目标更远。在这种情况下，我们不考虑列表。另外，我们可以确定每一个更有序的元素都会离目标更远，所以搜索可以缩短。
令人高兴的是，在通过目标之后做出此选择所需的测试总是在达到目标之前得到满足，因此在这两种情况下相同的代码就足够了。
这是一个优雅的解决方案，但它需要 O(n) 运行 时间来处理一棵 n 元素的树。
一个更复杂但渐进更快的解决方案依赖于树迭代器。可以构建可以在 O(h) 时间内初始化的迭代器，以从 h 是树的高度的任何元素开始。在目标处初始化其中两个，然后将一个向左移动另一个向右移动，始终选择最接近目标的下一个移动。当找到 k 个元素时停止。推进这些迭代器与有序遍历的每一步具有相同的时间复杂度：摊销常数时间。所以整个算法是O(h + k)。如果树是平衡的，这是 O(log n + k)，当 k << n.
时会好很多
我遇到了下面的 leetcode 问题，我对一些人用来解决它的方法有疑问。问题是： 给定一棵非空二叉搜索树和一个目标值，在BST中找到k个最接近目标的值。
注意： 给定的目标值是一个浮点数。
您可以假设 k 始终有效，即：k ≤ 总节点数。
您保证在 BST 中只有一组唯一的 k 值最接近目标。
所以，有些人所做的是，他们进行了有序遍历，同时维护了一个大小为 k 的最近元素队列。在顺序遍历期间，如果他们发现一个元素比队列中的第一个节点更接近目标，他们从队列中删除第一个节点并添加当前值。我的问题是，为什么他们与队列中的第一个元素进行比较？这是我所指的一些代码： https://leetcode.com/discuss/94472/inorder-one-linkedlist-java-solution-beat-85%25
据推测，队列中的第一个节点距离队列中元素的目标最远，只有在找到比它更近的节点时才需要更改队列。
中序遍历会先找到所有小于等于目标的元素。随着它的接近，新的、越来越近的元素将按排序顺序添加到列表的尾部。当它达到长度 k 后，在尾部添加一个新的更近的元素需要删除一个更远的元素。最远的是头部，所以它删除了。
搜索通过目标后，它开始看到距离目标越来越远的元素。每个人考虑的问题是它是否比列表中的目标更接近目标。假设 k=5 列表如下所示：
a <= b <= c <= d <= e (<= x?)
^
Target value somewhere between c and d
而下一个值 x >= e 刚刚被搜索发现。只有两种可能：
x比a更接近目标。在这种情况下，我们要删除a并在尾部添加x。x比a离目标更远。在这种情况下，我们不考虑列表。另外，我们可以确定每一个更有序的元素都会离目标更远，所以搜索可以缩短。
令人高兴的是，在通过目标之后做出此选择所需的测试总是在达到目标之前得到满足，因此在这两种情况下相同的代码就足够了。
这是一个优雅的解决方案，但它需要 O(n) 运行 时间来处理一棵 n 元素的树。
一个更复杂但渐进更快的解决方案依赖于树迭代器。可以构建可以在 O(h) 时间内初始化的迭代器，以从 h 是树的高度的任何元素开始。在目标处初始化其中两个，然后将一个向左移动另一个向右移动，始终选择最接近目标的下一个移动。当找到 k 个元素时停止。推进这些迭代器与有序遍历的每一步具有相同的时间复杂度：摊销常数时间。所以整个算法是O(h + k)。如果树是平衡的，这是 O(log n + k)，当 k << n.