一千萬個為什麽

搜索

在二進制搜索樹中打印K個最低值

我想弄清楚如何在二叉搜索樹中打印最低的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)

目前我的輸出只是按順序打印整棵樹

最佳答案

您需要稍微改變一下,以便了解在遞歸調用期間找到了多少元素。讓該函數返回找到的元素的數量並添加它們。您還需要檢查遞歸調用和當前節點元素之間的計數。

就像是:

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

轉載註明原文: 在二進制搜索樹中打印K個最低值