105. 从前序与中序遍历序列构造二叉树（中等）

Blind 75 › 105. 从前序与中序遍历序列构造二叉树（中等） （第 9 章）
文章工具

题目

给同一棵二叉树的前序遍历数组和中序遍历数组，请把整棵树重新构造出来，并返回根节点。

前序遍历的顺序是「根 → 左子树 → 右子树」，所以数组第一个数一定是整棵树的根；中序遍历的顺序是「左子树 → 根 → 右子树」，所以根在中序数组中的位置，会把数组切成「左子树节点」和「右子树节点」两段。

自造示例：preorder = [8,5,1,7,10,12]，inorder = [1,5,7,8,10,12]，构造结果按层序写作 [8,5,10,1,7,null,12]。

约束：节点数 1 ~ 3000；节点值 -3000 ~ 3000；两个数组等长，且所有节点值互不相同。

思路

一句话：前序负责“给出当前根是谁”，中序负责“圈出左子树和右子树的边界”。

最直白的做法：先取 preorder 的第一个值作为根，然后到 inorder 里找到它，把数组切成左右两段，再递归处理两段。这个方向完全正确，但如果每次递归都用线性扫描找根，每层都要扫一遍中序数组，最坏情况（树是一条链）会变成 O(n²)，n = 3000 时会明显变慢。

关键观察：题目保证所有节点值互不相同，所以「节点值 → 中序下标」是一个一一映射。预先用哈希表存好这个映射，以后定位切点只需要 O(1)。

更妙的是，preorder 本身就是「根、左子树、右子树」的顺序。维护一个全局指针，每递归一次消费一个根，先建左子树、再建右子树，指针的推进顺序就天然与递归顺序同步，不需要切分、复制数组。

解法

  1. 遍历 inorder，建立 pos[值] = 中序下标。
  2. 设指针 p = 0，表示当前要消费的 preorder 下标。
  3. 递归函数 build(left, right) 表示构造中序区间 [left, right] 对应的子树。
  4. 若 left > right，说明是空区间，返回空节点。
  5. 取 preorder[p] 作为根，p 加一；用 pos 找到根在中序中的位置 mid。
  6. 左子树对应 [left, mid-1]，右子树对应 [mid+1, right]；先递归左子树，再递归右子树。
ppreorder[p]inorder 区间动作
08[0,5]根 8，切点 3；左 [0,2]，右 [4,5]
15[0,2]根 5，切点 1；左 [0,0]，右 [2,2]
21[0,0]叶节点 1
37[2,2]叶节点 7
410[4,5]根 10，切点 4；右 [5,5]
512[5,5]叶节点 12

下图把上面 6 个步骤串成流程，并逐步演示：

105. 从前序与中序遍历序列构造二叉树（中等） 解法步骤流程图
图① 解法步骤流程图（共 6 步）。
105. 从前序与中序遍历序列构造二叉树（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
 unordered_map<int, int> pos;
 for (int i = 0; i < (int)inorder.size(); ++i) {
 pos[inorder[i]] = i;                 // 值 -> 中序下标
 }  int p = 0;                               // 先序里下一个待消费的根
 return build(preorder, pos, p, 0, (int)inorder.size() - 1);
 }  private:
 TreeNode* build(vector<int>& preorder,
 unordered_map<int, int>& pos,
 int& p,
 int left, int right) {
 if (left > right) return nullptr;        // 空区间：没有子树  int val = preorder[p++];                 // 先序第一个就是当前根
 TreeNode* root = new TreeNode(val);
 int mid = po
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。