3

使用 int 的二叉搜索树创建一个包含小于给定整数x值的所有整数的链表。

我试过什么？

1）残酷的解决方案（低效）

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。

问题是我该怎么办？

4

3 回答 3

1

伪代码。v是当前顶点，ans是答案列表，someTraversal是遍历树并返回其元素列表的方法。

  1. v := 根，ans := []
  2. 如果v.value > x
    那么v := v.left，转到2；
  3. ans.append(someTraversal (v.left))
  4. 如果v.value = x
    则返回ans;
  5. ans.append(v.value)
  6. v := v.right;
  7. 转到2；
于 2013-02-04T20:19:39.323 回答
1

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

  1. 创建一个新列表以保存结果
  2. 找到感兴趣的节点
  3. 将步骤 2 中找到的节点的左子树中的所有节点添加到列表中，使用您喜欢的任何遍历（按顺序、预排序等）
  4. 从步骤 2 中找到的节点的父节点开始，向上遍历所有父节点，一路添加每个节点，直到当前节点是根节点或其父节点左侧的节点
  5. 最后，将所有元素添加到步骤 4 中找到的节点的左侧，再次使用任意遍历
于 2013-02-04T20:41:31.867 回答
0

这是一个中序遍历的修改版本，它在节点的值大于 x 时终止。

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
于 2015-10-08T04:49:54.943 回答