此递归二进制搜索如何工作？为了在bst中找到第k个最小的节点

Question

前几天，我看到了这个二进制搜索/ dps解决方案，并且我很难理解其工作原理。

def kthSmallest(self, root, k):  # Binary Search - DPS
    def countNodes(node):
        if not node:
            return 0
        return 1 + countNodes(node.left) + countNodes(node.right)

    count = countNodes(root.left)
    if k <= count:
        return self.kthSmallest(root.left, k)
    elif k > count + 1:
        return self.kthSmallest(root.right, k - 1 - count)
    return root.val

Answer 1

首先让我们看一下countNodes内部定义的kthSmallest函数：它通过递归汇总以root和[ C0]。基本情况是没有节点，在这种情况下node.left返回0。

node.right背后的逻辑取决于BST的属性，即给定节点的密钥大于以其左子节点为根的子树中的所有节点，并且小于以其子节点为根的子树中的所有节点。对的孩子。在整个递归调用中保持不变的是，第k个最小的节点包含在以countNodes为根的子树中：在第一个调用中，kthSmallest是BST的根，因此该条件为true。然后，该算法计算root左子树中的节点数。通过BST属性，这是小于root的节点数。如果此数字大于或等于root，则第k个最小的节点必须在左子树中，因此算法递归到左子树中。如果数字+1小于root，则所寻找的节点必须位于正确的子树中，因此算法在该树中递归（因为对节点本身进行了计数，因此添加了+1）。此递归需要将k调整为k，因为k是小于k-1-count右子元素的节点数。最后，如果count + 1当前root是第k个最小的节点（因为它的左子树有k=count + 1个节点），并且该算法返回该节点的值。

这里是一个示例：假设我们有以下BST，并且正在寻找第3个最小的节点：

node

我们首先在根（3）上调用k-1，所以

  3.
 /  \
1    5
/\  / \
   4  6
   /\ /\
       8
       /\

为1，由于kthSmallest，该算法使用新的调整后的count递归到右子树中：

k = 3 > count + 1

现在k=3-1-1=1为1，并且由于

  5
 / \
4  6
/\ /\
    8

，该算法递归到左子树中：

count

现在k=1 <= 1为0，所以

4
/\

，并且算法返回count，它是序列k = count + 1中的第3个最小的节点。