python - 这种递归二分搜索是如何工作的？用于查找 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

标签： pythonpython-3.xbinary-search-tree

Answer 1

我们先来看看countNodes里面定义的函数kthSmallest：它root通过递归聚合以 和 为根的BST的节点数来计算以 为根的BST的节node.left点数node.right。基本情况是没有节点，在这种情况下countNodes返回 0。

背后的逻辑kthSmallest取决于 BST 的属性，即给定节点的键大于以左孩子为根的子树中的所有节点，并且小于以右孩子为根的子树中的所有节点。在整个递归调用中保持不变的是，第 k 个最小节点包含在以 为根的子树中root： 在第一次调用时，root是 BST 的根，所以这个条件成立。然后该算法计算 的左子树中的节点数root。根据 BST 属性，这是小于 的节点数root。如果这个数大于或等于k，则第 k 个最小的节点必须在左子树中，因此算法递归到左子树。如果数字 + 1 小于k，寻找的节点必须在右子树中，因此算法在那里递归（添加+1，因为节点本身被计​​算在内）。此递归需要调整k为，k-1-count因为count + 1节点数小于 的右子节点root。最后，如果k=count + 1当前node是第 k 个最小的节点（因为它的左子树有k-1节点）并且算法返回节点的值。

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

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

我们首先调用kthSmallest根 (3)，count1 也是如此，因为k = 3 > count + 1，算法递归到具有新调整的右子树k=3-1-1=1：

  5
 / \
4  6
/\ /\
    8

现在count是 1 并且因为k=1 <= 1，算法递归到左子树：

4
/\

现在count是 0 所以k = count + 1算法返回4，它是序列中第三小的节点1 3 4 5 6 8。