🔗 从前序与中序遍历序列构造二叉树

题目来源：105. 从前序与中序遍历序列构造二叉树 – 力扣（LeetCode）

---

📌 题目描述

给定两个整数数组 preorder 和 inorder，其中：

• preorder 是二叉树的先序遍历序列；
• inorder 是同一棵树的中序遍历序列。

请构造该二叉树并返回其根节点。

假设树中无重复元素，且输入序列一定合法。

---

✅ 示例解析

示例 1：

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

解释：

• 先序：[3, 9, 20, 15, 7] → 根 → 左 → 右
• 中序：[9, 3, 15, 20, 7] → 左 → 根 → 右
• 根为 3，左子树中序为 [9]，右子树中序为 [15,20,7]，递归构建即可。

示例 2：

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

示例 3：

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

---

⚠️ 提示

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• 所有元素唯一，且 inorder 是 preorder 对应树的中序遍历

---

💡 解法：递归 + 哈希表优化 —— O(n) 时间，O(n) 空间

class Solution {
    int[] preorder; // 全局保存先序数组，避免参数传递

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        Map<Integer, Integer> map = new HashMap<>();
        // 构建中序值到索引的映射，加速查找根位置
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return dfs(0, 0, inorder.length - 1, map);
    }

    /**
     * @param preRoot  当前子树在 preorder 中的根节点索引
     * @param inLeft   当前子树在 inorder 中的左边界
     * @param inRight  当前子树在 inorder 中的右边界
     * @param map      中序值到索引的哈希映射
     * @return         构建的子树根节点
     */
    public TreeNode dfs(int preRoot, int inLeft, int inRight, Map<Integer, Integer> map) {
        if (inLeft > inRight) {
            return null;
        }

        int rootVal = preorder[preRoot];
        int rootIdx = map.get(rootVal); // 根在中序中的位置

        TreeNode node = new TreeNode(rootVal);

        // 左子树：
        // - 先序根索引：preRoot + 1
        // - 中序范围：[inLeft, rootIdx - 1]
        node.left = dfs(preRoot + 1, inLeft, rootIdx - 1, map);

        // 右子树：
        // - 先序根索引 = preRoot + 1 + 左子树节点数
        // - 左子树节点数 = (rootIdx - 1) - inLeft + 1 = rootIdx - inLeft
        // - 所以右子树先序根索引 = preRoot + 1 + (rootIdx - inLeft)
        node.right = dfs(preRoot + 1 + (rootIdx - inLeft), rootIdx + 1, inRight, map);

        return node;
    }
}

✅ 关键点：

• 利用先序确定根，中序划分左右子树；
• 用哈希表 O(1) 定位根在中序中的位置；
• 通过左子树长度计算右子树在先序中的起始位置。

---

📊 复杂度分析

• 时间复杂度：O(n)
  • 建哈希表：O(n)
  • 每个节点被构建一次，每次递归操作 O(1)，共 n 个节点 → O(n)
• 空间复杂度：O(n)
  • 哈希表存储 n 个元素 → O(n)
  • 递归栈深度最坏为 O(n)（树退化为链表）

---

🧩 解题思路

核心思想：分治递归

1. 先序遍历的第一个元素一定是当前树的根节点。
2. 在中序遍历中找到该根的位置，其左侧为左子树，右侧为右子树。
3. 递归构建左右子树。

如何确定右子树在先序中的起始位置？

• 先序结构：[根][左子树][右子树]
• 左子树节点数 = rootIdx - inLeft
• 所以右子树在先序中的起始索引 = preRoot + 1 + (rootIdx - inLeft)

🌰 举例：
preorder = [3,9,20,15,7]，当前根 3 在 preorder[0]
中序中 3 的索引为 1，左子树长度 = 1 - 0 = 1
→ 右子树在先序中从 0 + 1 + 1 = 2 开始，即 20

为什么需要哈希表？

• 若每次在 inorder 中线性查找根的位置，时间复杂度会退化为 O(n²)。
• 哈希表将查找优化为 O(1)，整体达到 O(n)。