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

Question

让int的二进制搜索树创建小于给定整数的所有整数的链表x值。

我试过了吗？

1）残酷溶液（低效）

一种inorder访问的BST的，我插入列表中的一个节点对于int的的Bst， 每个整数，然后我释放从开始列表的每个节点X

2）更有效，但错误

我进行搜索，当我发现X，我创建一个列表与节点的左儿子的有序参观，我已经找到了X 。

很明显错误，例如考虑后续BST：

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

与此解决方案，如果x = 15我只考虑{12,13,14}，它会工作只是为X =根。

问题是我该怎么办？

Answer 1

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

1. ν：=根，ANS：= []
   
2. 如果 v.value> X
   然后ν：= v.left，转到 2;
   
3. ans.append（someTraversal（v.left））
   
4. 如果 v.value = X
   然后返回 ANS; （v.value）
   
5. v：= v。对;
   
6. goto 2;

Answer 2

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

1. 创建一个新的列表，以保存结果
2. 找到感兴趣的节点
3. 添加到列表中的所有节点在步骤2中找到的节点的左子树，使用任何遍历你喜欢（在顺序，预购等）
4. 从父母的父母开始在步骤2中找到的节点上行通过所有父节点添加每个节点，直到当前节点为其父节点的根节点或节点
5. 最后，将所有元素添加到其左侧步骤4中找到的节点再次使用任何遍历

Answer 3

这里是一个inorder遍历的修改版本，当节点的值> 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