在二进制搜索中打印K个最小值

Question

我想知道如何在二叉搜索树中打印最小的k值。我很难停止这种方法

代码：

def kthSmallestBST(node,k, count):
    if node == None or count == k:
        return
    else:
        kthSmallestBST(node.left, k, count)
        count += 1
        print node.data
        kthSmallestBST(node.right, k, count)
        count += 1


kthSmallestBST(BST, 3, 0)

目前我的输出只是按顺序打印整棵树

Answer 1

对count值的更改不会传播回调用者。您需要返回新计数：

def kthSmallestBST(node,k, count):
    if node is None or count >= k:
        return 0
    else:
        count += kthSmallestBST(node.left, k, count)
        if count < k:
            print node.data
            count += 1
        count += kthSmallestBST(node.right, k, count)
        return count

还要注意，您不需要同时使用k和{}。您可以去掉count，减量k，而不是递增{}，并将{}与0进行比较（而不是与count）。你得到的是：

^{pr2}$

Answer 2

您需要稍微改变一下，以便知道在递归调用期间找到了多少元素。让函数返回它找到的元素数，然后将它们相加。还需要检查递归调用和当前节点元素之间的计数。在

比如：

def kthSmallestBST(node, k, count):
    if node == None or count == k:
        return 0
    else:
        count += kthSmallestBST(node.left, k, count)
        if(count == k) 
            return count
        print node.data
        count += 1
        count += kthSmallestBST(node.right, k, count)
        return count

Answer 3

这是一个相当“函数式编程”的解决方案，但有一种方法是（懒洋洋地）按顺序生成树中的节点，然后使用itertools只获取第一个k

def inorder(tree):
    if not tree: return
    for node in inorder(tree.left): yield node
    yield tree
    for node in inorder(tree.right): yield node

def least(tree, k):
    return itertools.islice(inorder(tree), k)

如果您使用的是python3，那么可以使用“yield from”来缩短这个解决方案。在