力扣刷题#34-0105-从前序与中序遍历序列构造二叉树
题目
给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的前序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]3/ \9 20/ \15 7
我的思路
核心洞察：两种遍历各自给什么
| 遍历 | 顺序 | 我们能得到什么 |
|---|---|---|
| 前序 | 中 → 左 → 右 | 第一个元素一定是根 |
| 中序 | 左 → 中 → 右 | 根的左边是左子树，右边是右子树 |
两个信息一组合：
preorder = [3, 9, 20, 15, 7] → 3 是根
inorder = [9, 3, 15, 20, 7] → 9 是左子树，15,20,7 是右子树然后递归地处理"左子树"和"右子树"，一切重来
生活化类比：拼图游戏。手里有"前序卡片"和"中序卡片"各一叠。每次拿前序第一张当根，在中序堆里找到这张卡——左边一叠是左子树，右边一叠是右子树。递归地处理每一小叠。
我的 AC 代码（含注释）
class Solution {
public:// pos: 值 → 在 inorder 中的下标，O(1) 查找根的位置unordered_map<int, int> pos;// 用 [prel, prer] × [inl, inr] 描述当前要构建的子树区间TreeNode* build(vector<int>& preorder, vector<int>& inorder,int prel, int prer, int inl, int inr) {// ① 出口：前序区间空了（起点超过终点）→ 没有节点if (prel > prer) return nullptr;// ② 前序第一个元素 = 当前子树根TreeNode* root = new TreeNode(preorder[prel]);// ③ 在中序里找根的位置，计算左子树长度int rootpos = pos[root->val]; // 根在中序的下标int leftsize = rootpos - inl; // 根左边有几个元素 = 左子树长度// ④ 递归左子树：// preorder: 跳过根(prel+1)，占 leftsize 个位置// inorder: 从 inl 到 rootpos-1（根左边）root->left = build(preorder, inorder,prel + 1, prel + leftsize, inl, rootpos - 1);// ⑤ 递归右子树：// preorder: 跳过根+左子树，到区间末尾// inorder: 从 rootpos+1（根右边）到 inrroot->right = build(preorder, inorder,prel + leftsize + 1, prer, rootpos + 1, inr);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {// ⑥ 预处理：建立值 → 中序下标 的哈希表for (int i = 0; i < inorder.size(); i++)pos[inorder[i]] = i;// ⑦ 从完整区间开始递归return build(preorder, inorder, 0, preorder.size() - 1, 0,inorder.size() - 1);}
};
逐步拆解（用例子走一遍）
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
第一层：build(0, 4, 0, 4)
| 步骤 | 计算 | 结果 |
|---|---|---|
| 根 | preorder[0] |
3 |
| 根在中序位置 | pos[3] |
1 |
| leftsize | 1 - 0 |
1 |
| 左子树 | build(1, 1, 0, 0) |
preorder[1..1]=[9] |
| 右子树 | build(2, 4, 2, 4) |
preorder[2..4]=[20,15,7] |
第二层：build(1, 1, 0, 0) 和 build(2, 4, 2, 4)
build(1,1,0,0)：根=9，leftsize=0，左右都是空区间 → 叶子build(2,4,2,4)：根=20（preorder[2]），pos[20]=3，leftsize=3-2=1- 左子树
build(2,2,2,2)→ preorder[2..2]=[15] - 右子树
build(4,4,4,4)→ preorder[4..4]=[7]
- 左子树
递归树全貌
build(0,4,0,4) → root=3
├── build(1,1,0,0) → root=9（叶子）
└── build(2,4,2,4) → root=20├── build(2,2,2,2) → root=15（叶子）└── build(4,4,4,4) → root=7（叶子）
为什么需要四个边界参数？
每次递归处理"两段子数组"（preorder 一段 + inorder 一段），各自需要起点和终点：
| 参数 | 含义 |
|---|---|
prel |
当前子树在 preorder 中的起点 |
prer |
当前子树在 preorder 中的终点 |
inl |
当前子树在 inorder 中的起点 |
inr |
当前子树在 inorder 中的终点 |
递归 = 不断把这两个区间切小，直到空。
为什么用哈希表？
如果每次都在 inorder 里 for 扫描找根的位置，每层 O(n)，总共 O(n²)。用哈希表把查找降到 O(1)，总时间 O(n)。
这是"空间换时间"的典型应用——先用 O(n) 空间建表，换 O(n) 的总时间。
复杂度分析
| 维度 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 每个节点构建一次，哈希查找 O(1) |
| 空间复杂度 | O(n) | 哈希表 O(n) + 递归栈 O(h) |
关键点总结
| 关键点 | 说明 |
|---|---|
| 前序的作用 | 第一个元素 = 根 |
| 中序的作用 | 根的左边 = 左子树，右边 = 右子树 |
| leftsize | 根在中序的位置 - inl = 左子树长度 |
| 左子树前序 | [prel+1, prel+leftsize] |
| 右子树前序 | [prel+leftsize+1, prer] |
| 哈希表 | 值→中序下标，O(1) 查找 |
本文档由 AI 辅助生成，作者提供问题，思路和代码，AI仅负责文本修饰，综合获得以上内容。