好的，我们这次来深入剖析一道非常经典且考察频率极高的题目——LeetCode 第 105 题「从前序与中序遍历序列构造二叉树」。

这道题是理解二叉树遍历和递归思想的绝佳范例。我会从最基础的概念开始，一步步引导你理解问题本质、构建解题思路，并最终写出代码。

题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历（根-左-右）结果，inorder 是同一棵树的中序遍历（左-根-右）结果。请你构造并返回这棵二叉树的根节点。

示例 1：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

（输出的层次遍历结果，null 表示空节点）

示例 2：

输入: preorder = [-1], inorder = [-1]
输出: [-1]

循序渐进讲解

第一步：理解核心前提与关键线索

要解决这个问题，我们必须深刻理解两种遍历方式的特性：

1. 先序遍历 (Preorder)：[根节点, [左子树的前序遍历结果], [右子树的前序遍历结果]]

   • 第一个元素永远是整棵树的根节点。

2. 中序遍历 (Inorder)：[[左子树的中序遍历结果], 根节点, [右子树的中序遍历结果]]

   • 一旦我们知道了根节点的值，就可以在 inorder 数组中找到它。这个根节点左边的所有元素构成了左子树，右边的所有元素构成了右子树。

关键线索： 如果我们知道了根节点，并且知道了左子树和右子树的大小，我们就可以在 preorder 中划分出属于左子树和右子树的区间。

重要前提： 题目假设树中没有重复的元素。这样，我们才能通过值在 inorder 中唯一地确定根节点的位置。

第二步：通过一个具体例子来手动模拟

让我们以示例一为例，手动构建这棵树，这是理解算法最关键的一步。

已知：
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

我们的目标是构建出下面这棵树：

    3
   / \
  9  20
    /  \
   15   7

手动构建过程：

1. 确定根节点：

   • 根据先序遍历的特性，preorder 的第一个元素 3 就是整棵树的根节点。

2. 在中序遍历中找到根节点，并划分左右子树：

   • 在 inorder 数组中找到值 3，它的索引位置是 1（从0开始计数）。
   • 在 inorder 中：
     • 3 左边的 [9] 构成了根节点 3 的左子树的中序遍历结果。
     • 3 右边的 [15, 20, 7] 构成了根节点 3 的右子树的中序遍历结果。
   • 我们同时可以知道左右子树的大小：
     • 左子树的大小：1 个元素 (9)
     • 右子树的大小：3 个元素 (15, 20, 7)

3. 在先序遍历中划分左右子树：

   • 我们已经知道根节点是 preorder[0]（即 3）。
   • 紧跟着根节点的，应该是左子树的前序遍历，然后才是右子树的前序遍历。
   • 左子树有 1 个元素，所以左子树的前序遍历就是 preorder 中从索引 1 开始，长度为 1 的区间：[9]。
   • 右子树有 3 个元素，所以右子树的前序遍历就是 preorder 中从索引 2 开始，长度为 3 的区间：[20, 15, 7]。

   现在，我们得到了两个子问题：

   • 子问题1（构建左子树）：
     • 左子树的 preorder = [9]
     • 左子树的 inorder = [9]
   • 子问题2（构建右子树）：
     • 右子树的 preorder = [20, 15, 7]
     • 右子树的 inorder = [15, 20, 7]

4. 递归地解决子问题：

   • 解决子问题1（构建左子树）：
     • 根节点是 9。
     • 在 inorder [9] 中找到 9，它的左边和右边都是空的。所以这是一个没有左右子树的叶子节点。
     • 将节点 9 作为根节点 3 的左孩子。
   • 解决子问题2（构建右子树）：
     • 根节点是 20。
     • 在 inorder [15, 20, 7] 中找到 20，其左边是 [15]（左子树），右边是 [7]（右子树）。
     • 在 preorder [20, 15, 7] 中，左子树（大小1）是 [15]，右子树（大小1）是 [7]。
     • 递归构建：
       • 20 的左孩子：preorder=[15], inorder=[15] -> 根节点为 15 的叶子节点。
       • 20 的右孩子：preorder=[7], inorder=[7] -> 根节点为 7 的叶子节点。
     • 将节点 20 作为根节点 3 的右孩子。

5. 完成构建：递归过程结束，整棵树构建完成。

第三步：抽象出递归算法步骤

基于上面的模拟，我们可以总结出递归函数的定义和步骤。

1. 递归函数定义：

   • buildTree(preorder, preStart, preEnd, inorder, inStart, inEnd)
   • 作用：根据前序遍历数组 preorder 中从 preStart 到 preEnd 的部分，和中序遍历数组 inorder 中从 inStart 到 inEnd 的部分，构建二叉树，并返回根节点。

2. 递归终止条件：

   • 如果 preStart > preEnd 或 inStart > inEnd，说明当前区间是空的，返回 null。

3. 递归主体逻辑（当前层逻辑）：

   • 创建根节点：当前子树的根节点值是 preorder[preStart]。
   • 在中序数组中找到根节点：在 inorder 的 [inStart, inEnd] 区间内，找到根节点的值，设其索引为 index。
   • 计算左子树大小：leftSize = index - inStart。这个数字至关重要！
   • 递归构建左子树：
     • 左子树的 preorder 区间：从 preStart + 1 开始，长度为 leftSize，所以结束于 preStart + 1 + leftSize - 1 = preStart + leftSize。
     • 左子树的 inorder 区间：从 inStart 开始，到 index - 1 结束。
     • 递归调用：root.left = buildTree(preorder, preStart+1, preStart+leftSize, inorder, inStart, index-1)
   • 递归构建右子树：
     • 右子树的 preorder 区间：从 preStart + leftSize + 1 开始，到 preEnd 结束。
     • 右子树的 inorder 区间：从 index + 1 开始，到 inEnd 结束。
     • 递归调用：root.right = buildTree(preorder, preStart+leftSize+1, preEnd, inorder, index+1, inEnd)
   • 返回根节点：返回当前创建好的 root。

第四步：代码实现（带详细注释）

为了提升效率，我们先用一个哈希表 (HashMap) 记录每个值在中序遍历数组中的索引，这样每次查找根节点位置的时间复杂度是 O(1)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 哈希表，用于快速定位中序遍历数组中值对应的索引
    private HashMap<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 初始化哈希表
        indexMap = new HashMap<>();
        int n = inorder.length;
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        // 调用递归函数，初始区间为整个数组
        return buildTreeHelper(preorder, 0, n - 1, inorder, 0, n - 1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd,
                                   int[] inorder, int inStart, int inEnd) {
        // 1. 递归终止条件：如果区间无效，返回 null
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        // 2. 创建当前子树的根节点（前序遍历第一个元素）
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        // 3. 在中序遍历中找到根节点的位置
        int rootIndexInInorder = indexMap.get(rootVal);

        // 4. 计算左子树的大小（中序数组中根节点左边的元素个数）
        int leftSubtreeSize = rootIndexInInorder - inStart;

        // 5. 递归构建左子树
        // 左子树在前序中的区间: [preStart + 1, preStart + leftSubtreeSize]
        // 左子树在中序中的区间: [inStart, rootIndexInInorder - 1]
        root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftSubtreeSize,
                                  inorder, inStart, rootIndexInInorder - 1);

        // 6. 递归构建右子树
        // 右子树在前序中的区间: [preStart + leftSubtreeSize + 1, preEnd]
        // 右子树在中序中的区间: [rootIndexInInorder + 1, inEnd]
        root.right = buildTreeHelper(preorder, preStart + leftSubtreeSize + 1, preEnd,
                                   inorder, rootIndexInInorder + 1, inEnd);

        // 7. 返回构建好的根节点
        return root;
    }
}

第五步：复杂度分析

• 时间复杂度：O(n)，其中 n 是树中节点的个数。我们每个节点只创建一次，并且通过哈希表查找位置的时间是 O(1)。
• 空间复杂度：O(n)。哈希表存储 n 个元素的索引需要 O(n) 空间。递归栈的深度取决于树的高度，在最坏情况下（树退化成链表）深度为 O(n)，平均情况下为 O(log n)。所以总空间复杂度为 O(n)。

总结与思考

这道题的精髓在于利用前序遍历确定根节点，再利用中序遍历确定左右子树的边界。通过“左子树大小”这个桥梁，将大规模问题分解成结构相同的小规模问题，这正是递归（分治）思想的完美体现。

你可以尝试一下它的变体题目 LeetCode 第 106 题「从中序与后序遍历序列构造二叉树」，思路几乎完全一致，只是后序遍历的根节点在序列的最后一个位置。这能很好地检验你是否真正理解了本题的核心思想。