在二叉搜索树中查找小于给定值的所有值的算法

Question

Having a Binary Search Tree of int create a linked list of all the integers less than a given integer x value.

我试过什么？

1)残酷的解决方案(低效)

安inorder访问 BST，我在列表中为 Bst 中的每个整数插入一个节点， 然后我释放列表中从 x 开始的每个节点

2)效率更高但错误

我进行搜索，当我找到 x 时，我创建了一个列表，其中顺序访问了我找到 x 的节点的左儿子。

这显然是错误的，例如考虑以下 BST:

                         10
                        /  \
                       9    11
                      /       \
                     5         15
                    / \        / \
                   1   8      13  19
                             /  \
                            12  14

使用此解决方案，如果 x=15 我只考虑 {12,13,14}，它只适用于 x=root。

问题是我该怎么做？

Answer 1

如果存储每个节点的父节点，可以实现更高效的解决方案，只要不关心结果列表中元素的顺序:

1. 创建一个新列表来保存结果
2. 找到感兴趣的节点
3. 将在第 2 步中找到的节点的左子树中的所有节点添加到列表中，使用您喜欢的任何遍历(按顺序、前序等)
4. 从第 2 步找到的节点的父节点开始，遍历所有父节点，依次添加每个节点，直到当前节点是根节点或其父节点左侧的节点
5. 最后，再次使用任意遍历，将所有元素添加到第 4 步找到的节点的左侧