资讯详情

力扣刷题#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仅负责文本修饰，综合获得以上内容。