AcWing刷题笔记-17-重建二叉树 2026.04.17 算法蒟蒻的成长记录，AcWing

AcWing 刷题笔记：17. 重建二叉树

“根据遍历序列重建二叉树”。给定前序和中序遍历，唯一确定一棵二叉树。

前序遍历的第一个元素总是根节点。用它在中序遍历中定位，就能分出左子树和右子树的范围。

---

题目思路

• 前序遍历：根 -> 左 -> 右
• 中序遍历：左 -> 根 -> 右

步骤：

1. 前序第一个是根，在中序中找到它的位置。
2. 左边是左子树，右边是右子树。
3. 递归处理左右子树。

---

技巧

用哈希表存储中序遍历的值到索引的映射，快速查找根位置，避免每次线性搜索。

定义类内两个数组,将函数中的数组传入,编写 build 或者 dfs 函数的时候就不需要单独传入数组了

---

C++ 代码

class Solution {
public:
    unordered_map<int, int> hash;  // 存储中序遍历值到索引的映射，快速查找根节点位置
    vector<int> preorder, inorder;  // 保存前序和中序遍历数组
    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
        preorder = _preorder;
        inorder = _inorder;
        auto n = inorder.size();
        if (n == 0) return nullptr;  // 边界检查：空输入
        // 建立哈希表：中序值 -> 索引
        for (int i = 0; i < n; ++i) hash[inorder[i]] = i;

        // 递归构建树，前序 [0, n-1]，中序 [0, n-1]
        return build(0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    // 递归函数：根据前序和中序范围构建子树
    TreeNode* build(int l1, int r1, int l2, int r2) {
        if (l1 > r1) return nullptr;  // 递归边界：前序范围无效

        // 前序第一个是根节点
        TreeNode* root = new TreeNode(preorder[l1]);
        int i = hash[preorder[l1]];  // 根在中序中的位置

        // 左子树：前序 [l1+1, l1 + (i - l2)]，中序 [l2, i-1]
        root->left = build(l1 + 1, l1 + (i - l2), l2, i - 1);
        // 右子树：前序 [l1 + (i - l2) + 1, r1]，中序 [i+1, r2]
        root->right = build(l1 + (i - l2) + 1, r1, i + 1, r2);

        return root;
    }
};

---

复杂度分析

• 时间：O(n)，哈希表 O(n)，递归 O(n)
• 空间：O(n)，哈希表和递归栈

---

易错点

• 递归边界：l1 > r1 返回 nullptr
• 索引计算：左子树长度 i - l2，右子树从 l1 + (i - l2) + 1
• 哈希表用 unordered_map，查找 O(1)

---

总结

这题是二叉树重建的基础。掌握前序+中序的递归分治，就能轻松解决。后序+中序类似，只是根在最后。

下次遇到遍历重建题，优先用哈希表优化查找！