DSA Interview Prep · 课时

第 K 小、区间和与 BST 转有序数组

Q: 「第 K 小、区间和与 BST 转有序数组」课时是免费的吗？

是的 — 「第 K 小、区间和与 BST 转有序数组」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

Q: 学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

Q: 「第 K 小、区间和与 BST 转有序数组」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

利用有序的中序遍历，以 O(k) 的时间查找第 k 小元素，并以 O(log n + k) 的时间计算区间内的值之和。

第 4 / 4 课13 个步骤

第 K 小、区间和与 BST 转有序数组 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

BST 中的第 k 小元素

BST 中的第 k 小元素（LeetCode #230）是一道经典问题，直接利用了中序遍历的排序性质。由于中序遍历会按升序访问节点，我们只需在遍历过程中统计节点数量，并返回计数达到 k 时的值。时间复杂度为 O(h + k)，其中 h 是树的高度（用于到达最左侧节点），k 是中序遍历过程中移动的步数。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_smallest(root, k):
    count = [0]
    result = [None]

    def inorder(node):
        if not node or result[0] is not None:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1))  # 1
print(kth_smallest(root, 2))  # 2

第 k 小元素：使用栈的迭代方法

迭代版本使用显式栈的中序遍历模式。不断压入左侧节点直到遇到空节点，然后弹出节点并计数。当计数达到 k 时，返回当前节点的值。这可以避免非常深的树触发 Python 的递归深度限制，时间复杂度同样为 O(h + k)，空间复杂度为 O(h)。面试官经常会在递归版本之后要求实现迭代版本。

def kth_smallest_iterative(root, k):
    stack = []
    curr = root
    count = 0
    while curr or stack:
        while curr:             # go as far left as possible
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()      # process node
        count += 1
        if count == k:
            return curr.val
        curr = curr.right       # move to right subtree
    return -1  # k out of range

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3))  # 3

BST 中的第 k 大元素

第 k 大元素使用反向中序遍历（右子树 → 根节点 → 左子树），按降序访问节点。移动 k 步后返回当前节点的值。它与第 k 小元素的做法对称，时间复杂度为 O(h + k)。如果知道树的大小，也可以计算 kth_smallest(root, total_count - k + 1)，但反向中序方法更加优雅。

def kth_largest(root, k):
    count = [0]
    result = [None]

    def reverse_inorder(node):
        if not node or result[0] is not None:
            return
        reverse_inorder(node.right)   # visit LARGER values first
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        reverse_inorder(node.left)

    reverse_inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_largest(root, 1))  # 4 (largest)
print(kth_largest(root, 2))  # 3 (2nd largest)

BST 的范围和

BST 的范围和（LeetCode #938）要求计算 [low, high] 内所有值的总和。请利用 BST 性质进行剪枝：如果当前节点的值小于 low，那么整个左子树也都小于 low——跳过左子树。如果当前值大于 high，则跳过右子树。这种方法可以剪去许多分支，比完整的中序扫描更高效。

def range_sum_bst(root, low, high):
    if not root:
        return 0
    total = 0
    if low <= root.val <= high:
        total += root.val
    if root.val > low:    # left subtree might have values >= low
        total += range_sum_bst(root.left, low, high)
    if root.val < high:   # right subtree might have values <= high
        total += range_sum_bst(root.right, low, high)
    return total

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15))  # 7+10+15 = 32

统计范围内的节点数

统计范围 [low, high] 内的节点数遵循相同的剪枝逻辑。另一种方法是在中序数组上使用 bisect_left/右边界二分查找——但直接遍历 BST 的时间复杂度为 O(log n + k)，而先转换为数组始终需要 O(n) 时间。除非需要回答大量范围查询，否则请选择直接遍历；在需要回答大量查询时，构建带有子树计数的增强 BST，可以将每次查询的复杂度降至 O(log n)。

def count_range(root, low, high):
    if not root:
        return 0
    count = 0
    if low <= root.val <= high:
        count += 1
    if root.val > low:
        count += count_range(root.left, low, high)
    if root.val < high:
        count += count_range(root.right, low, high)
    return count

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(count_range(root, 6, 15))  # 7, 10, 15 = 3

BST 转排序数组（完整算法）

将 BST 转换为排序数组的时间复杂度为 O(n)，空间复杂度为 O(n)。请使用中序遍历，并对每个值调用 append。它是多步骤问题的起点，例如“合并两个 BST”、“查找 BST 的中位数”或“检查两个 BST 是否具有相同的中序序列”。生成的数组支持按索引 O(1) 访问、二分查找和双指针技巧，而 BST 本身无法直接提供这些操作。

def bst_to_sorted(root):
    result = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)
    inorder(root)
    return result

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(bst_to_sorted(root))  # [1, 3, 4, 5, 6, 8, 9]

# Binary search on the resulting sorted array:
import bisect
arr = bst_to_sorted(root)
print(bisect.bisect_left(arr, 6))   # 4 (index of 6)

增强型 BST：子树大小

增强型 BST 会在每个节点存储额外信息，例如其子树的大小。有了子树大小，查找第 k 小值可以达到 O(log n)：在每个节点处，如果左子树大小为 k-1，则当前节点就是答案；如果左子树大小 >= k，则递归处理左子树；否则减去左子树大小后递归处理右子树。这正是竞赛编程中所使用的顺序统计树背后的数据结构。

class AugNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.size = 1  # subtree size

def get_size(node):
    return node.size if node else 0

def update_size(node):
    if node:
        node.size = 1 + get_size(node.left) + get_size(node.right)

def kth_smallest_aug(root, k):
    left_size = get_size(root.left)
    if k == left_size + 1:
        return root.val      # current node is kth
    elif k <= left_size:
        return kth_smallest_aug(root.left, k)
    else:
        return kth_smallest_aug(root.right, k - left_size - 1)

print('Augmented BST: O(log n) kth smallest with subtree sizes')

查找 BST 中两个节点之间的所有值

要返回严格位于两个节点 p 和 q 之间的所有值（其中 p.val < q.val），可以将中序遍历与范围剪枝结合起来：经过 p.val 后开始收集值，经过 q.val 后停止。这是范围求和的通用化方法，可以在 O(h + k) 时间内得到位于两个查询值之间的有序序列。

def values_between(root, low, high):
    result = []
    def inorder(node):
        if not node:
            return
        if node.val > low:    # might be values > low on left
            inorder(node.left)
        if low < node.val < high:  # strictly between
            result.append(node.val)
        if node.val < high:   # might be values < high on right
            inorder(node.right)
    inorder(root)
    return result

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
print(values_between(root, 6, 15))  # [7, 10, 12]

BST 的中位数

BST 的中位数是中序遍历结果中的中间值。对于包含 n 个节点的 BST，中位数位于索引 n // 2 处（索引从 0 开始）。您可以收集完整的有序数组并通过索引访问中位数，也可以分两次遍历：第一次统计 n 个节点，第二次进行中序遍历，在到达第 n // 2 个节点时停止。另一种方法是使用查找第 k 小值的算法，并令 k = n // 2 + 1。

def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

def median_of_bst(root):
    n = count_nodes(root)
    if n == 0:
        return None
    k = n // 2 + 1  # (n+1)/2-th element for odd, n/2+1-th for even
    return kth_smallest(root, k)

def kth_smallest(root, k):
    count = [0]; result = [None]
    def inorder(node):
        if not node or result[0] is not None: return
        inorder(node.left)
        count[0] += 1
        if count[0] == k: result[0] = node.val; return
        inorder(node.right)
    inorder(root); return result[0]

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
print(median_of_bst(root))  # 4 (middle of [1,3,4,5,8])

距离目标值最近的 K 个值

查找 BST 中距离目标值最近的 k 个值。一种双指针方法是：将 BST 转换为有序数组，然后使用大小为 k 的滑动窗口。另一种方法是使用大小为 k 的最大堆，压入距离，并在大小超过 k 时弹出元素。有序数组方法的时间复杂度为 O(n)，实现简单；堆方法的时间复杂度为 O(n log k)，但适用于流式场景。

import heapq

def closest_k_values(root, target, k):
    # Collect sorted values
    arr = []
    def inorder(node):
        if not node: return
        inorder(node.left)
        arr.append(node.val)
        inorder(node.right)
    inorder(root)

    # Two-pointer sliding window of size k
    left, right = 0, k - 1
    while right < len(arr) - 1:
        if abs(arr[left] - target) <= abs(arr[right + 1] - target):
            break  # left is closer, don't advance
        left += 1
        right += 1
    return arr[left:right + 1]

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_k_values(root, 3.7, 2))  # [3, 4]

利用后继顺序性质

许多 BST 问题都可以归结为查找有序序列中的下一个或前一个元素——通过 BST 导航可以在 O(log n) 时间内完成这些操作。我们之前构建的迭代器可以使 next 操作的摊销复杂度达到 O(1)。结合查找第 k 小值、范围求和以及最近值相关知识，您可以通过思考“中序遍历的有序性如何简化这个问题？”来解决大多数 BST 面试题。这种元模式就是解决 BST 问题的指南。

# Meta-pattern for BST problems:
# Step 1: What sorted-order property does this exploit?
# Step 2: Is in-order (ascending) or reverse in-order (descending) needed?
# Step 3: Can I prune using BST ordering to avoid O(n) scan?

# Quick reference:
# kth smallest  -> in-order, stop at kth node
# kth largest   -> reverse in-order, stop at kth node
# range sum     -> in-order + BST pruning
# closest value -> walk toward target, track best
# median        -> kth with k = n//2+1
# sorted array  -> full in-order
# validate      -> in-order prev check or min/max bounds
print('Sorted in-order is the universal BST problem tool')

快速检查

测试您对本课数据结构与算法——编程面试准备相关概念的理解。

在交互式课程中回答

课程回顾

本课中您学习了：使用中序遍历和逆中序遍历在 O(h+k) 时间内查找第 k 小和第 k 大元素，使用BST 剪枝进行范围求和以高效处理范围查询，以及将 BST 转换为有序数组，作为基于数组的算法基础。接下来我们将学习堆和优先队列。

免费开始

用 AI 导师学习 Python — 免费

在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。

课程: 30
课程: 120

免费开始学习查看完整课程

常见问题解答