Python递归——如何提前退出

Question

我一直在玩 BST(二叉搜索树)，我想知道如何提前退出。以下是我为找到第 k 个最小值而编写的代码。它递归调用子节点的find_smallest_at_k，stack只是一个传入函数的列表，将所有元素按顺序相加。目前这个解决方案按顺序遍历所有节点，然后我必须从这个函数之外的“堆栈”中选择第 k 个项目。

def find_smallest_at_k(self, k, stack, i):
    if self is None:
        return i

    if (self.left is not None): 
        i = self.left.find_smallest_at_k(k, stack, i) 

    print(stack, i)
    stack.insert(i, self.data)
    i += 1
    if i == k: 
        print(stack[k - 1]) 
        print "Returning" 

    if (self.right is not None): 
        i = self.right.find_smallest_at_k(k, stack, i) 

    return i 

它是这样称呼的，

our_stack = []
self.root.find_smallest_at_k(k, our_stack, 0) 
return our_stack[k-1] 

我不确定是否可以提前退出该函数。如果我的 k 是 1，我真的不必遍历所有节点然后找到第一个元素。从外部函数传递列表也感觉不对 - 感觉就像将指针传递给 C 中的函数。有人能提出比我目前所做的更好的替代方案吗？

Answer 1

将列表作为参数传递:如果您使函数尾递归，则将列表作为参数传递是一种很好的做法。否则没有意义。对于 BST，其中有两个潜在的递归函数调用要完成，这是一个有点高的要求。

否则您可以返回列表。我没有看到变量 i 的必要性.无论如何，如果你绝对需要返回多个值，你总是可以使用像这样的元组 return i, stack还有这个i, stack = root.find_smallest_at_k(k) .

快进:对于快进，请注意 BST 父节点的右节点总是比父节点大。因此，如果你总是在正确的 child 上下降树，你最终会得到一个不断增长的值序列。因此第一个k该序列的值必然是最小的，因此向右k 毫无意义一个序列中的次数或更多次。

即使在你下坡的中间，你有时也会向左走，走超过k是没有意义的右边的时间。 BST 属性确保如果您向右走，层次结构中下方的所有后续数字都将大于父级。向右走k次或更多是没有用的。

代码: 这是一个快速制作的伪python代码。未经测试。

def findKSmallest( self, k, rightSteps=0 ):
    if rightSteps >= k: #We went right more than k times
        return []
    leftSmallest = self.left.findKSmallest( k, rightSteps ) if self.left != None else []
    rightSmallest = self.right.findKSmallest( k, rightSteps + 1 ) if self.right != None else []
    mySmallest = sorted( leftSmallest + [self.data] + rightSmallest )
    return mySmallest[:k]

根据我的评论编辑另一个版本。

def findKSmallest( self, k ):
    if k == 0:
        return []
    leftSmallest = self.left.findKSmallest( k ) if self.left != None else []
    rightSmallest = self.right.findKSmallest( k - 1 ) if self.right != None else []
    mySmallest = sorted( leftSmallest + [self.data] + rightSmallest )
    return mySmallest[:k]

请注意，如果 k==1 ，这确实是最小元素的搜索。向右移动，将立即返回 [] , 这没有任何贡献。