DSA Interview Prep · 课时

验证 BST 与中序性质

Q: 「验证 BST 与中序性质」课时是免费的吗？

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

Q: 「验证 BST 与中序性质」这节课中我会学到什么？

使用沿树向下传递的最小值和最大值边界验证二叉树是否为 BST，并检查中序遍历是否产生有序序列。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

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

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

Q: 「验证 BST 与中序性质」课时需要多长时间？

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

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

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

使用沿树向下传递的最小值和最大值边界验证二叉树是否为 BST，并检查中序遍历是否产生有序序列。

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

BST 验证问题

验证 BST（LeetCode #98）是一道经典的面试题，许多候选人都会在这里出错。朴素方法只检查每个节点的值是否大于其左子节点且小于其右子节点，但这种局部检查并不充分。子树中的某个节点可能满足局部规则，却违反全局 BST 性质。正确的解决方案是将有效的最小值/最大值边界沿树向下传递。

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

# Why local check fails:
#     5
#    / \
#   1   4
#      / \
#     3   6
# Node 4's children (3, 6) satisfy local rule,
# but 4 < 5 and is in the RIGHT subtree -- BST violated!
print('Local check is insufficient -- use min/max bounds')

最小值/最大值边界方法

在递归过程中向下传递下界和上界。对于每个节点，请验证 low < node.val < high。递归进入左子树时，将上界更新为 node.val（左子树必须更小）；递归进入右子树时，将下界更新为 node.val（右子树必须更大）。从 low = -infinity 和 high = +infinity 开始。

def is_valid_bst(root, low=float('-inf'), high=float('inf')):
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

# Valid BST:
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
print(is_valid_bst(valid))  # True

# Invalid BST (3 is in wrong subtree conceptually):
invalid = TreeNode(5)
invalid.left = TreeNode(1)
invalid.right = TreeNode(4)
invalid.right.left = TreeNode(3)
invalid.right.right = TreeNode(6)
print(is_valid_bst(invalid))  # False (4 < 5 in right subtree)

中序遍历验证

另一种验证方法利用 BST 的中序有序性质：收集中序序列，并验证它是否严格递增。这种方法简洁且易于理解。不过，它需要 O(n) 的额外空间来存储序列。优化版本会在遍历过程中使用一个 prev 指针，检查每一对相邻元素，而无需存储整个序列。

def is_valid_bst_inorder(root):
    prev = [float('-inf')]

    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:  # not strictly increasing
            return False
        prev[0] = node.val
        return inorder(node.right)

    return inorder(root)

valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
valid.left.left = TreeNode(1)
valid.left.right = TreeNode(4)
print(is_valid_bst_inorder(valid))   # True

invalid = TreeNode(5)
invalid.left = TreeNode(6)  # 6 > 5 in left subtree!
print(is_valid_bst_inorder(invalid)) # False

比较两种验证方法

最小值/最大值边界方法的时间复杂度为 O(n)，空间复杂度为 O(h)（仅需存储调用栈中的边界）。中序前驱指针方法的时间复杂度同样为 O(n)，空间复杂度同样为 O(h)。两者都是最优方法。最小值/最大值方法更通用，在扩展到带有额外约束的问题时也能保持清晰。在面试中，请准备好介绍这两种方法并讨论其中的权衡——能够意识到替代方案是一个很好的表现。

# Both approaches:
# Time: O(n) -- visit each node once
# Space: O(h) -- call stack depth
# h = O(log n) balanced, O(n) skewed

# When to choose which:
# min/max bounds:
#   - Cleaner for trees with constraints beyond BST
#   - No global state (purely functional)
# in-order prev:
#   - More intuitive (sorted sequence check)
#   - Easier to convert to iterative with a stack

print('Both O(n) time, O(h) space -- choose by clarity')

恢复 BST：两个交换的节点

恢复 BST（LeetCode #99）用于修复恰好有两个节点被交换的 BST。在中序遍历期间，顺序正确的 BST 会产生一个有序序列。如果两个节点被交换，就会出现一次或两次违反顺序的情况，其中 prev.val > current.val。第一次违反顺序时的第一个节点，以及最后一次违反顺序时的第二个节点，就是位置错误的两个节点——交换它们的值即可。

def recover_tree(root):
    first = second = prev = None

    def inorder(node):
        nonlocal first, second, prev
        if not node:
            return
        inorder(node.left)
        if prev and prev.val > node.val:
            if not first:
                first = prev    # first violator
            second = node       # always update second
        prev = node
        inorder(node.right)

    inorder(root)
    # Swap values of the two misplaced nodes
    if first and second:
        first.val, second.val = second.val, first.val

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(2)  # 2 and 3 are swapped
recover_tree(root)
print(root.val, root.right.left.val)  # 2, 3 (fixed)

将 BST 的中序序列转换为排序数组

将 BST 转换为排序数组非常简单：执行中序遍历并收集各个值。这项 O(n) 时间、O(n) 空间的操作，是在 BST 数据上使用排序数组算法（二分查找、双指针）的快捷方式。它通常是多部分 BST 问题的基础步骤，例如“合并两个 BST”或“查找 BST 的中位数”。

def bst_to_sorted_array(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(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print(bst_to_sorted_array(root))  # [1, 2, 3, 4, 5, 6, 7]

合并两个 BST

要将两个 BST 合并为一个排序数组，请先分别在 O(n) 和 O(m) 时间内将它们转换为排序数组，然后使用归并排序的合并步骤，在 O(n+m) 时间内合并这两个排序数组。总时间复杂度为 O(n+m)。如果需要将结果构建为平衡 BST，请将合并后的排序数组传给“排序数组转 BST”算法。将问题分解为简单的子问题，是清晰且便于面试中讲解的解决方案的标志。

def merge_two_bsts(root1, root2):
    def inorder(node, arr):
        if not node:
            return
        inorder(node.left, arr)
        arr.append(node.val)
        inorder(node.right, arr)

    arr1, arr2 = [], []
    inorder(root1, arr1)
    inorder(root2, arr2)

    # Merge two sorted arrays
    merged = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            merged.append(arr1[i]); i += 1
        else:
            merged.append(arr2[j]); j += 1
    merged.extend(arr1[i:])
    merged.extend(arr2[j:])
    return merged

r1 = TreeNode(2); r1.left = TreeNode(1); r1.right = TreeNode(4)
r2 = TreeNode(3); r2.left = TreeNode(0); r2.right = TreeNode(5)
print(merge_two_bsts(r1, r2))  # [0, 1, 2, 3, 4, 5]

统计 BST 范围内的节点数

统计值处于范围 [low, high] 内的节点数量。暴力中序扫描的时间复杂度为 O(n)。利用 BST 性质的方法会进行剪枝：如果当前节点的值小于 low，就无需检查左子树（其中的所有值也都小于 low）。同样地，当当前值大于 high 时，可以剪去右子树。平均情况下，时间复杂度为 O(log n + k)，其中 k 是匹配节点的数量。

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 may have values >= low
        total += range_sum_bst(root.left, low, high)
    if root.val < high:  # right subtree may 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

重复值与严格/非严格 BST

标准 BST 不变量使用严格不等式：左子树的值严格更小，右子树的值严格更大。有些问题允许重复值，将重复值放在左子树中（左 <= 根节点）或右子树中（根节点 < 右）。验证 BST 时，请始终检查题目对 BST 的定义。最小值/最大值边界方法通过调整边界检查是严格比较还是包含边界，可以同时处理这两种变体。

# Strict BST (LeetCode default): left < root < right
def is_valid_strict(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    if not (lo < root.val < hi):  # STRICT inequalities
        return False
    return (is_valid_strict(root.left, lo, root.val) and
            is_valid_strict(root.right, root.val, hi))

# Non-strict BST (allows duplicates in right): left <= root < right
def is_valid_nonstrict(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    if not (lo <= root.val < hi):  # NOTE: <= for left side
        return False
    return (is_valid_nonstrict(root.left, lo, root.val + 1) and
            is_valid_nonstrict(root.right, root.val, hi))

print('Always clarify strict vs non-strict with interviewer')

中序遍历：通用的 BST 工具

中序遍历是 BST 问题中的万能工具。每当 BST 问题询问排序顺序、第 k 个元素、范围查询或序列性质时，请考虑中序扫描（或反向中序扫描）是否能直接得到答案。大多数 BST 专属问题都可以归结为：按排序顺序遍历，并在每一步执行某项操作。快速识别这种对应关系是面试中的一项重要技能。

# Problems solved elegantly with in-order:
# 1. Validate BST: check prev <= curr during in-order
# 2. Kth smallest: count k steps in in-order
# 3. Kth largest: count k steps in REVERSE in-order
# 4. Closest value to target: find crossover in in-order
# 5. BST to sorted array: collect in-order into list
# 6. Recover BST: find 1-2 violations in in-order
# 7. Sum of range [lo, hi]: accumulate during in-order

# The key insight: in-order visits BST nodes in sorted order.
# All sorted-order reasoning translates to in-order DFS.
print('In-order = sorted access = foundation of BST reasoning')

BST 中的最接近值

查找值与给定目标最接近的节点。请利用 BST 的排序关系：从根节点开始，跟踪目前见过的最接近值，并向目标值所在的方向移动（目标值较小时向左，较大时向右）。这种 O(h) 方法比中序扫描更高效，也展示了如何有效利用 BST 性质来剪枝搜索空间。

def closest_value(root, target):
    closest = root.val
    curr = root
    while curr:
        if abs(curr.val - target) < abs(closest - target):
            closest = curr.val
        if target < curr.val:
            curr = curr.left
        elif target > curr.val:
            curr = curr.right
        else:
            break  # exact match
    return closest

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

快速检查

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

课程回顾

在本课中，您学习了：使用最小值/最大值边界验证 BST（避免局部检查陷阱）、用于验证的中序前驱指针替代方法，以及中序遍历作为处理范围和、最接近值和合并操作的通用 BST 工具。接下来，我们将利用 BST 中序遍历的性质查找第 k 小元素。

常见问题解答