在二元搜索树中查找与目标数最接近的k个数
我遇到了以下leetcode问题，我对一些人用来解决它的方法有一个问题。问题是：给定一个非空二叉查找树和一个目标值，在BST中找到最接近目标的k个值。
注意：给定的目标值是浮点。
您可以假设k始终有效，即：k≤总节点。
保证BST中只有一组最接近目标的唯一k值。
所以，有些人所做的是，他们在保持k大小的最近元素队列的同时，按顺序遍历。在顺序遍历过程中，如果发现某个元素比队列中的第一个节点更接近目标，则会从队列中删除第一个节点并添加当前值。我的问题是，为什么它们会与队列中的第一个元素进行比较？以下是我所指内容的一些代码：html" target="_blank">https://leetcode.com/discuss/94472/inorder-one-linkedlist-java-solution-beat-85%
共有2个答案
据推测，队列中的第一个节点距离队列中元素的目标最远，只有在发现比该节点更近的节点时，队列才需要更改。
顺序遍历将首先找到小于或等于目标的所有元素。随着时间的推移，新的、越来越近的元素将按排序顺序添加到列表的尾部。达到长度k后，在尾部添加一个新的closer元素需要删除一个更远的元素。距离最远的是头部，因此它会删除该头部。
搜索通过目标后，它开始看到离目标越来越远的元素。每一个都要考虑的问题是，它是否比列表中已经列出的更接近目标。假设k=5，列表如下所示：
a <= b <= c <= d <= e (<= x?)
^
Target value somewhere between c and d
和下一个值
>
x比a更接近目标。在这种情况下，我们要删除a并在尾部添加x。
距离目标的距离比距离目标的距离远。在这种情况下，我们不去管清单。此外，我们可以确定，每隔一步，顺序元素都会离目标更远，因此可以缩短搜索时间。
令人高兴的是，在通过目标后进行此选择所需的测试总是在到达目标之前得到满足，因此在这两种情况下，相同的代码就足够了。
这是一个优雅的解决方案，但对于包含n个元素的树，它有O（n）个运行时。
更复杂但渐近更快的解决方案依赖于树迭代器。可以构建可以在O（h）时间内初始化的迭代器，以从任何元素开始，其中h是树的高度。在目标位置初始化其中两个，然后向左移动一个，向右移动另一个，始终选择最靠近目标的位置进行下一步移动。当找到k个元素时停止。推进这些迭代器与按序遍历的每个步骤具有相同的时间复杂性：摊销常数时间。所以整个算法是O（hk）。如果树是平衡的，这就是O（log n k），当k时更好
-
我有一个非常简单的二叉树 我实现了一个函数来查找树中离目标最近的数字（19）： 结果显然应该是22，但我得到了8。令人惊讶的是，当我打印所有以下“最接近”的数字时，函数似乎工作正常：它打印：8、14、22。但为什么它不返回最新的clostest数字：22？
-
问题内容： 说我有一个清单。我想找到3个最接近的数字，例如6.5。然后返回的值将是。 在python中找到一个最接近的数字并不是那么棘手，可以使用 但是我试图不绕这个循环找到k个最接近的数字。有pythonic方法可以完成上述任务吗？ 问题答案： 简短的答案 该 heapq.nsmallest（） 函数将整齐，有效地做到这一点： 本质上是这样说的：“给我三个与 6.5 绝对差值最小的输入值”。 算
-
这种方法在确定树是否为BST时是错误的吗？节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。我的代码是：
-
给定一个未排序的数组，我试图找到最接近数组中位数的 K 个元素。我在线性运行时间内找不到解决方案。 这里的中位数是6。 答案是2,3,4,5,6。 任何帮助或提示将不胜感激。
-
这是我第一次使用这个平台提问。我想知道以下代码有什么问题，它们没有在主代码末尾打印出目标数字的索引。发生了什么？祝那些阅读本文的人度过愉快的一天。
-
我希望在BST中找到具有特定值的节点的父节点。我的节点类具有左右属性项（即值/键）。 查找父级的想法是这样的： 1）如果值（key）不存在，则返回无，无 2）如果根等于值（key），则返回无，根 3）否则查找值（key）并返回（par， node），其中par是父级和节点 我的函数是这样的: 当 为“无”时，如何处理该问题？