构造二叉树与 BST 特性

从前序 + 中序构造（105）

前序序列的第一个元素一定是根；中序序列里根把序列劈成左右两半。利用这两条，每一步都能确定根和两个区间的边界：

找根：前序区间的第一个元素就是当前子树的根；
切中序：在中序区间里找到根的位置 mid，左边是左子树（left 个元素），右边是右子树；
切前序：前序区间跳过根之后，紧跟着的 left 个属于左子树，其余属于右子树；
递归：对切出的四个新区间重复上述过程。

用 [3,9,20,15,7]（前序）与 [9,3,15,20,7]（中序）画区间示意：

前序: [ 3 | 9 | 20 15 7 ]
       根   左   右
              ↕ 用中序算出左子树长度=1
中序: [ 9 | 3 | 15 20 7 ]
       左   根   右

递归：左子树 (前序[9], 中序[9])  →  叶子 9
      右子树 (前序[20,15,7], 中序[15,20,7])  →  同理继续切

每层递归都要"在中序里找根的位置"，如果线性扫描，整体退化到 O(n²)。用 HashMap 预存中序的值 → 下标映射，查找 O(1)，总复杂度 O(n)：

class Solution {
    private Map<Integer, Integer> inorderIndex = new HashMap<>();
 
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 值互异是本题前提，可放心建映射
        for (int i = 0; i < inorder.length; i++) {
            inorderIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length,
                     inorder, 0, inorder.length);
    }
 
    // 区间统一用左闭右开 [l, r)，避免 +1/-1 打架
    private TreeNode build(int[] preorder, int pl, int pr,
                           int[] inorder,  int il, int ir) {
        if (pl >= pr) return null;                 // 区间空：没有节点
        TreeNode root = new TreeNode(preorder[pl]); // 前序第一个是根
        int mid = inorderIndex.get(preorder[pl]);   // 根在中序中的位置
        int leftSize = mid - il;                    // 左子树节点数
 
        // 前序：[pl+1, pl+1+leftSize) 是左子树，其后是右子树
        // 中序：根左侧是左子树，右侧是右子树
        root.left  = build(preorder, pl + 1, pl + 1 + leftSize,
                           inorder,  il, mid);
        root.right = build(preorder, pl + 1 + leftSize, pr,
                           inorder,  mid + 1, ir);
        return root;
    }
}

区间记法是本题最大的坑，两个要点：整条递归链只用一种开闭约定（示例用左闭右开），以及四个区间的端点全由 leftSize 推导，不要凭感觉写 pl + mid 这类混合表达式。

从中序 + 后序构造（106）

和 105 完全对称，只有两处镜像改动：

根在后序区间的最后一个：postorder[pr - 1]；
切前序改成切后序：后序是"左右根"，根前面的 leftSize 个是左子树，再前面是右子树。

private TreeNode build(int[] inorder, int il, int ir,
                       int[] postorder, int pl, int pr) {
    if (pl >= pr) return null;
    TreeNode root = new TreeNode(postorder[pr - 1]); // 后序最后一个是根
    int mid = inorderIndex.get(root.val);
    int leftSize = mid - il;
 
    // 中序：[il, mid) 左子树，[mid+1, ir) 右子树
    // 后序：[pl, pl+leftSize) 左子树，[pl+leftSize, pr-1) 右子树
    root.left  = build(inorder, il, mid,
                       postorder, pl, pl + leftSize);
    root.right = build(inorder, mid + 1, ir,
                       postorder, pl + leftSize, pr - 1); // pr-1 排除根
    return root;
}

顺便记住组合规则：必须有中序才能唯一确定一棵二叉树。前序+后序构造的结果不唯一（只有一个孩子的节点无法判断它是左还是右），这是原理题的高频考点。

BST 三特性与验证（98）

二叉搜索树靠三条特性吃饭：

有序性：中序遍历结果是严格递增序列；
局部性：对任意节点，左子树所有值 < 节点值 < 右子树所有值（不是只比左右孩子）；
查找性：查找、插入、删除都可以走单边路径，平均 O(log n)。

98 验证二叉搜索树是最能暴露"局部性"理解偏差的题。只比父子和为什么错：

        5
       / \
      3   8
           \
            4        4 > 3（与祖父的关系），却出现在 5 的右子树里
                     只比父子：4 < 8 ✓、父 8 无左子树判断……误判为合法

4 比 8 小、也比父链上所有节点小，但它 violates 了"必须在 5 的右子树且大于 5"。正确做法是给每个节点传上下界：进入左子树时收紧上界为当前值，进入右子树时收紧下界为当前值：

public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}
 
// validate：node 子树的所有值必须落在 (low, high) 开区间内
private boolean validate(TreeNode node, Integer low, Integer high) {
    if (node == null) return true;
    if (low  != null && node.val <= low)  return false;
    if (high != null && node.val >= high) return false;
    // 向左：上界收紧为自己；向右：下界收紧为自己
    return validate(node.left, low, node.val)
        && validate(node.right, node.val, high);
}

用 Integer 包装类型是让 null 表示"无界"，避免被 Integer.MIN_VALUE 这类真实边界值坑到。另一种解法是中序遍历 + 检查严格递增，实现也不难，但要小心"前驱比较"里保存的变量初始化和相等值判断。

插入（701）与删除（450）

插入（701）：BST 的插入就是一次没找到目标的查找——沿路比较往单边走，走到空位就把新节点挂上去。返回值设计成 TreeNode（返回"处理完的子树根"），让父节点直接用返回值接住重挂的子树，省掉记录父指针：

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);  // 空位：新节点挂这里
    if (val < root.val) root.left  = insertIntoBST(root.left, val);
    else                root.right = insertIntoBST(root.right, val);
    return root;                                 // 原根不变时原样返回
}

删除（450）：难点全在"删掉之后谁来补位"。先把五种情况列全：

情况	场景	处理
①	树空 / 找不到目标	返回 null，无事发生
②	目标是叶子	直接删，返回 null
③	只有左孩子	左孩子顶上
④	只有右孩子	右孩子顶上
⑤	左右孩子都在	用右子树最左节点（中序后继）替换值，再在右子树里删掉那个节点

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;               // ① 没找到
    if (key < root.val) {
        root.left  = deleteNode(root.left, key);
        return root;
    }
    if (key > root.val) {
        root.right = deleteNode(root.right, key);
        return root;
    }
    // 命中目标节点
    if (root.left == null) return root.right;    // ②④ 叶子或只有右孩子
    if (root.right == null) return root.left;    // ③ 只有左孩子
    // ⑤ 两个孩子都在：找右子树最左节点接班
    TreeNode successor = root.right;
    while (successor.left != null) successor = successor.left;
    root.val = successor.val;                    // 值替换
    root.right = deleteNode(root.right, successor.val); // 右子树中删掉接班人
    return root;
}

"返回值接住子树"的技巧在这里再次发挥作用：每个分支都 return 处理后的子树根，父层 root.left = ... 原地拼接，不需要任何父指针或额外判断。删除是 BST 章节实现细节最多的题，写完务必对五种情况逐一构造用例验证。

中序有序性的延伸运用

"中序遍历 BST 得到有序序列"这一条性质，本身就是一把解题钥匙：

题号	题名	有序性的用法
530	BST 的最小绝对差	中序序列相邻元素差的最小值
501	BST 中的众数	中序序列里找最长连续相等段
538	把 BST 转换为累加树	反向中序（右根左）从大到小累加
108	有序数组转 BST	有序数组取中点建根，左右递归

这类题的共同套路：不要在树上搜索，先沿中序把树"拉直"成有序数组（或边遍历边维护前驱），问题的形状从"树"退化成"序列"，难度直线下降。

LeetCode 题单

题号	题名	一句话考点
105	从前序与中序遍历序列构造二叉树	前序找根、中序切分，HashMap 缓存下标
106	从中序与后序遍历序列构造二叉树	根在后序末尾，区间端点镜像推导
654	最大二叉树	数组最大值为根、左右递归，同构造套路
617	合并二叉树	双树同步递归，返回新根
98	验证二叉搜索树	上下界收紧，或中序严格递增
700	二叉搜索树中的搜索	利用有序性走单边，O(h)
701	二叉搜索树中的插入操作	走到空位挂节点，返回值接子树
450	删除二叉搜索树中的节点	五种情况，后继节点接班
669	修剪二叉搜索树	越界时借子树整体顶替
530/501/538	中序有序性三连	树问题退化成序列问题

参考

代码随想录 · 二叉树专题