构造与二叉搜索树

◎

本节目标

用区间关系构造普通二叉树，用严格有序约束处理二叉搜索树。

第七章公共示例树

根 1，左右孩子 2、3，节点 2 的左右孩子为 4、5。

        1
       / \
      2   3
     / \
    4   5

本栏的两类问题都使用递归，但依据不同。普通二叉树的构造依赖遍历序列给出的结构关系；二叉搜索树则额外拥有“左子树更小、右子树更大”的全局有序约束。

识别信号

• 给出两种遍历序列，要求还原一棵树；
• 给出有序数组，要求生成高度平衡的 BST；
• 判断某棵树是否满足 BST 的严格有序性；
• 询问 BST 中按从小到大排序后的第 k 个节点；
• 当前子问题可由数组下标区间或允许值范围完整描述。

问题模型与核心不变量

公共树的前序为 1, 2, 4, 5, 3，中序为 4, 2, 5, 1, 3，因此可按两个区间重建相同结构。它本身不是 BST：根 1 的左孩子 2 已能被局部比较发现。一般情形仍需传递祖先范围，因为更深节点可能满足父子局部关系，却违反祖先界限。

构造普通二叉树时，前序区间首元素是根；该根在中序区间的位置将左右子树分开。传递半开区间 [left, right)，空区间自然表示空树，也避免反复复制数组。

BST 的约束作用于整棵子树，不只是父子节点。验证时，每个节点都要落在祖先传下来的严格范围内。构造平衡 BST 时，选择当前有序区间的中点为根；中序遍历 BST 总会按严格递增顺序访问节点，因此可在访问第 k 个节点时停止。

通用模板

build(left, right):
    if left >= right:
        return null
    middle = left + (right - left) / 2
    root = 新节点(nums[middle])
    root.left = build(left, middle)
    root.right = build(middle + 1, right)
    return root

validate(node, lower, upper):
    if node 为空:
        return true
    if node.val 不在 (lower, upper):
        return false
    return validate(node.left, lower, node.val)
       and validate(node.right, node.val, upper)

构造前序与中序树时，中序位置表使根位置查询为常数期望时间；左右子树大小再把前序和中序的半开区间同时切开。

模板变体

• 前序首元素定根，中序位置定左右子树规模，递归不切片复制数组。
• 有序数组选中点，递归构造近似等高的 BST。
• BST 验证把当前节点值收紧为一侧子树的上界或下界。
• BST 第 K 小用显式栈完成中序遍历，弹出第 k 个节点即返回。

母题序列

按必学顺序练习：

1. 从前序与中序遍历序列构造二叉树（必学）：用根位置拆分两组下标区间。
2. 将有序数组转换为二叉搜索树（必学）：用中点递归构造平衡结构。
3. 验证二叉搜索树（必学）：把祖先范围传给整棵子树。
4. 二叉搜索树中第 K 小的元素（必学）：按中序顺序访问并提前停止。

常见误区

• 构造题每层切出新的子数组，造成额外复制和更高常数。
• 只比较父子节点，漏掉跨越多层祖先的 BST 违规。
• 用 INT_MIN、INT_MAX 作为严格边界，误判取到极值的合法节点。
• 中序遍历到第 k 个节点后继续完整遍历，放弃了 BST 的早停优势。

迁移方向

当构造条件不再唯一或需要处理重复值时，要先明确额外规则；当 BST 需要频繁插入、删除或区间查询时，才需要学习平衡树等数据结构，它们不属于本章范围。