查找二叉查找树中小于给定值的所有值的算法
让一个整数的二进制搜索树创建一个包含所有小于给定整数x值的整数的链表。
我试过什么？
1)粗暴的解决方案(效率低下)
BST 的顺序访问，我在列表中为每个整数 int the BST 插入一个节点，然后我从 x 开始释放列表中的每个节点
2)效率更高但错误
我进行了一次搜索，当我找到x时，我创建了一个列表，其中有序地访问了我找到x的节点的左边的子节点。
这显然是错误的，例如考虑到以下BST：
10
/ \
9 11
/ \
5 15
/ \ / \
1 8 13 19
/ \
12 14
对于这个解决方案，如果x=15，我只考虑{12,13,14}，它仅适用于x=root。
问题是我怎么做？
共有3个答案
下面是一个inorder遍历的修改版本，当节点的值为
def nums_less_than(n, x, l=None):
if l == None:
l = []
if n.left:
nums_less_than(n.left, x, l)
if n.value < x:
l.append(n.value)
if n.right:
nums_less_than(n.right, x, l)
return l
伪代码。v是当前顶点，ans是答案列表，someTraversal是遍历树并返回其元素列表的方法。
-
< li>v := root，ans := []
< li >如果虚拟值
如果存储每个节点的父节点，可以实现更高效的解决方案，只要不在乎结果列表中元素的顺序:
- 新建列表保存结果
- 找到感兴趣的节点
- 使用您喜欢的任何遍历（按顺序、按顺序等）将步骤2中找到的节点的左子树中的所有节点添加到列表中
- 从第2步找到的节点的父节点开始，向上遍历所有父节点，按方式添加每个节点，直到当前节点要么是根节点，要么是父节点左边的节点
- 最后，将所有元素添加到步骤4中找到的节点的左侧，再次使用任何遍历
-
我试图递归地在二叉树中找到最小值（不是二叉查找树）。让我困惑的是基本情况。如果TreeNode t为空，返回什么？因为我将使用返回的值将其与当前的最小值进行比较（我认为），我相信我返回的内容很重要。
-
我正在做一个AlgoExpert挑战，我已经花时间自己解决它，看了关于它的视频讲座，我觉得我有一个很好的理解，但我在递归和树遍历方面的技能现在很低（这就是我工作的原因）。 这是提示 编写一个函数，该函数接受二进制搜索树（BST）和目标整数值，并返回与BST中包含的目标值最接近的值。每个BST节点都有一个整数值、一个左子节点和一个右子节点。其子节点本身是有效的BST节点或无/空 目标：12 这是我目
-
我正在努力实现二叉搜索树。完成实现所需的功能之一是重新平衡功能。 根据规范，该功能的工作方式如下: rebalance（） 方法应创建一个平衡树，从而将偏度降低为零。平衡树是指在整个树中，左子树和右子树的大小相差不超过1（即，每个子树也是平衡的）。 为了平衡树，rebalance（） 方法应反复将根值移动到较小的子树，并将最小/最大值从较大的子树移动到根，直到树平衡。然后，它应该以递归方式平衡两个
-
本文向大家介绍JavaScript数据结构与算法之二叉树实现查找最小值、最大值、给定值算法示例，包括了JavaScript数据结构与算法之二叉树实现查找最小值、最大值、给定值算法示例的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了JavaScript数据结构与算法之二叉树实现查找最小值、最大值、给定值算法。分享给大家供大家参考，具体如下： 运行结果： 感兴趣的朋友可以使用在线HTML/CS
-
主要内容：什么是二叉排序树？,使用二叉排序树查找关键字,二叉排序树中插入关键字,二叉排序树中删除关键字,总结前几节介绍的都是有关静态 查找表的相关知识，从本节开始介绍另外一种查找表—— 动态查找表。 动态查找表中做查找操作时，若查找成功可以对其进行删除；如果查找失败，即表中无该关键字，可以将该关键字插入到表中。 动态查找表的表示方式有多种，本节介绍一种使用树结构表示动态查找表的实现方法—— 二叉排序树（又称为 “二叉查找树”）。 什么是二叉排序树？ 二叉排序树要么是空 二叉树，要么具有如下特点：
-
我们已经看到了两种不同的方法来获取集合中的键值对。回想一下，这些集合实现了 map 抽象数据类型。我们讨论的 map ADT 的两个实现是在列表和哈希表上的二分搜索。在本节中，我们将研究二叉查找树作为从键映射到值的另一种方法。 在这种情况下，我们对树中项的确切位置不感兴趣，但我们有兴趣使用二叉树结构来提供高效的搜索。