Kam*_*mal 2 algorithm binary-search-tree
我遇到了以下 leetcode 问题，我对一些人用来解决它的方法有疑问。问题是：给定一个非空的二叉搜索树和一个目标值，在BST中找到最接近目标的k个值。
注意：给定的目标值是一个浮点数。
您可以假设 k 始终有效，即： k ? 总节点数。
你保证在 BST 中只有一组唯一的 k 值最接近目标。
因此，有些人所做的是，他们在保持最近元素的 ak 大小队列的同时进行了有序遍历。在顺序遍历过程中，如果发现比队列中的第一个节点更接近目标的元素，则从队列中删除第一个节点并添加当前值。我的问题是，为什么它们与队列中的第一个元素进行比较？这是我所指的一些代码：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。在这种情况下，我们不考虑列表。此外，我们可以确定每一个进一步的有序元素都会离目标更远，因此可以缩短搜索时间。
令人高兴的是，在通过目标之后做出这个选择所需的测试总是在达到目标之前得到满足，所以在这两种情况下，相同的代码就足够了。
这是一个优雅的解决方案，但对于n元素树，它的运行时间为 O(n) 。
一个更复杂但渐近更快的解决方案依赖于树迭代器。可以构建可以在 O(h) 时间内初始化的迭代器，以从h树的高度的任何元素开始。在目标处初始化其中两个，然后向左移动另一个向右移动，始终选择最接近目标的下一个移动。k找到元素后停止。推进这些迭代器与有序遍历的每一步具有相同的时间复杂度：摊销常数时间。所以整个算法是O(h + k)。如果树是平衡的，这是 O(log n + k)，当 时好得多k << n。