【面试高频题】二叉树的重建：由前序+中序遍历和后序+中序遍历重建二叉树

文字目录

• 一、问题背景与核心思想
• • 1.1 问题描述
  • 1.2 核心原理
• 二、由前序 + 中序还原二叉树
• • 2.1 原理分析
  • 2.2 递归实现
  • 2.3 执行过程追踪
  • 2.4 非递归实现（迭代 + 栈）
  • 2.5 执行过程追踪
• 三、由后序 + 中序还原二叉树
• • 3.1 原理分析
  • 3.2 递归实现
  • 3.3 执行过程追踪
  • 3.4 非递归实现（迭代 + 栈）
  • 3.5 执行过程追踪
• 四、两种方法对比
• • 4.1 切割规则对比
  • 4.2 序列切割示意图
• 五、算法复杂度分析
• • 5.1 时间复杂度
  • 5.2 空间复杂度
  • 5.3 递归 vs 非递归
• 六、完整可运行代码

一、问题背景与核心思想

1.1 问题描述

给定二叉树的两种遍历序列，还原（重建）出唯一的二叉树结构。

本文讨论两种经典组合：

⚠️ 前提条件：树中所有节点的值各不相同，否则无法唯一定位根节点在中序序列中的位置。

1.2 核心原理

三种遍历方式的特征：

前序遍历：[ 根 | 左子树序列 | 右子树序列 ]
中序遍历：[ 左子树序列 | 根 | 右子树序列 ]
后序遍历：[ 左子树序列 | 右子树序列 | 根 ]

关键结论：

• 前序序列的第一个元素 = 当前树的根节点
• 后序序列的最后一个元素 = 当前树的根节点
• 根节点在中序序列中的位置 = 左子树与右子树的分割线

只要知道根节点，就能在中序序列中把左右子树分开；知道左右子树的节点数量，就能在前/后序序列中切出对应的子序列；然后递归重建。

二、由前序 + 中序还原二叉树

2.1 原理分析

以下面的例子为例：

前序遍历：[ 3, 9, 20, 15, 7 ]
中序遍历：[ 9, 3, 15, 20, 7 ]

第一步：确定根节点

前序序列首元素 = 3，即根节点为 3。

前序：[ 3 | 9, 20, 15, 7 ]
↑
根节点

第二步：在中序序列中定位根节点

在中序序列中找到 3 的位置（下标 = 1）：

中序：[ 9 | 3 | 15, 20, 7 ]
↑
根节点
左子树长度=1 右子树长度=3

第三步：切割前序序列

已知左子树长度 = 1，右子树长度 = 3：

前序：[ 3 | 9 | 20, 15, 7 ]
←1→ ←—3—→
左子 右子树序列

第四步：递归重建

对右子树继续递归：

• 前序 [20, 15, 7] → 根 = 20
• 中序 [15, 20, 7] → 20 在位置 1 → 左子树 [15]，右子树 [7]

最终还原结果：

3
/ \\
9 20
/ \\
15 7

2.2 递归实现

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution_PreIn {
private:
// 存储中序序列中每个值的下标，查询 O(1)
unordered_map<int, int> inorderIndex;

/**
* 递归重建
* preorder : 前序序列
* preLeft : 当前子树在前序中的起始下标
* preRight : 当前子树在前序中的结束下标
* inLeft : 当前子树在中序中的起始下标
* inRight : 当前子树在中序中的结束下标
*/
TreeNode* build(const vector<int>& preorder,
int preLeft, int preRight,
int inLeft, int inRight) {
// 递归终止：子序列为空
if (preLeft > preRight) return nullptr;

// 1. 前序首元素即为当前根节点
int rootVal = preorder[preLeft];
TreeNode* root = new TreeNode(rootVal);

// 2. 在中序序列中定位根节点
int inRootIdx = inorderIndex[rootVal];

// 3. 计算左子树节点数量
int leftSize = inRootIdx – inLeft;

// 4. 递归重建左子树
// 前序左子树范围：[preLeft+1, preLeft+leftSize]
// 中序左子树范围：[inLeft, inRootIdx-1]
root->left = build(preorder,
preLeft + 1, preLeft + leftSize,
inLeft, inRootIdx – 1);

// 5. 递归重建右子树
// 前序右子树范围：[preLeft+leftSize+1, preRight]
// 中序右子树范围：[inRootIdx+1, inRight]
root->right = build(preorder,
preLeft + leftSize + 1, preRight,
inRootIdx + 1, inRight);

return root;
}

public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 预处理：建立中序值→下标的哈希映射
for (int i = 0; i < n; i++) {
inorderIndex[inorder[i]] = i;
}
return build(preorder, 0, n – 1, 0, n – 1);
}
};

2.3 执行过程追踪

以 preorder=[3,9,20,15,7]，inorder=[9,3,15,20,7] 为例：

递归过程（树形展开）：

build(pre[0..4], in[0..4])
rootVal=3, inRootIdx=1, leftSize=1
├─ 左子树 build(pre[1..1], in[0..0])
│ rootVal=9, inRootIdx=0, leftSize=0
│ ├─ 左子树 build(pre[2..1]) → nullptr
│ └─ 右子树 build(pre[2..1]) → nullptr
│ return Node(9)
└─ 右子树 build(pre[2..4], in[2..4])
rootVal=20, inRootIdx=3, leftSize=1
├─ 左子树 build(pre[3..3], in[2..2])
│ return Node(15)
└─ 右子树 build(pre[4..4], in[4..4])
return Node(7)
return Node(20)
return Node(3)

递归参数追踪表：

2.4 非递归实现（迭代 + 栈）

TreeNode* buildTreeIterative_PreIn(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) return nullptr;

TreeNode* root = new TreeNode(preorder[0]);
stack<TreeNode*> stk;
stk.push(root);

int inIdx = 0; // 中序序列的指针

for (int i = 1; i < (int)preorder.size(); i++) {
TreeNode* node = stk.top();
TreeNode* child = new TreeNode(preorder[i]);

// 若栈顶节点值 ≠ 中序当前值，说明还在向左走
if (node->val != inorder[inIdx]) {
node->left = child; // 作为左子节点
} else {
// 回溯：弹出所有已访问完左子树的节点，直到找到右子节点的父节点
while (!stk.empty() && stk.top()->val == inorder[inIdx]) {
node = stk.top();
stk.pop();
inIdx++;
}
node->right = child; // 作为右子节点
}
stk.push(child);
}
return root;
}

2.5 执行过程追踪

以 preorder=[3,9,20,15,7]，inorder=[9,3,15,20,7] 为例：

非递归迭代过程追踪：

迭代算法核心逻辑：前序顺序 = 根→左→右，遇到新节点先尝试接到栈顶的左边；若栈顶值等于中序当前值，说明左子树已完成，回溯找到右子节点的父节点。

前序：[ 3, 9, 20, 15, 7 ] 索引 i = 0,1,2,3,4
中序：[ 9, 3, 15, 20, 7 ] 指针 inIdx 从 0 开始

完整追踪（含回溯细节）：

构建结果验证：

3
/ \\
9 20
/ \\
15 7

节点挂载关系汇总：

三、由后序 + 中序还原二叉树

3.1 原理分析

以下面的例子为例：

后序遍历：[ 9, 15, 7, 20, 3 ]
中序遍历：[ 9, 3, 15, 20, 7 ]

第一步：确定根节点

后序序列末元素 = 3，即根节点为 3。

后序：[ 9, 15, 7, 20 | 3 ]
↑
根节点

第二步：在中序序列中定位根节点

在中序序列中找到 3 的位置（下标 = 1）：

中序：[ 9 | 3 | 15, 20, 7 ]
↑
根节点
左子树长度=1 右子树长度=3

第三步：切割后序序列

已知左子树长度 = 1，右子树长度 = 3：

后序：[ 9 | 15, 7, 20 | 3 ]
←1→ ←—3—→ 根
左子 右子树序列

第四步：递归重建

对右子树继续递归：

• 后序 [15, 7, 20] → 根 = 20
• 中序 [15, 20, 7] → 20 在位置 1 → 左子树 [15]，右子树 [7]

最终还原结果：

3
/ \\
9 20
/ \\
15 7

与前序+中序还原结果完全一致 ✅

3.2 递归实现

class Solution_PostIn {
private:
unordered_map<int, int> inorderIndex;

/**
* 递归重建
* postorder : 后序序列
* postLeft : 当前子树在后序中的起始下标
* postRight : 当前子树在后序中的结束下标
* inLeft : 当前子树在中序中的起始下标
* inRight : 当前子树在中序中的结束下标
*/
TreeNode* build(const vector<int>& postorder,
int postLeft, int postRight,
int inLeft, int inRight) {
// 递归终止：子序列为空
if (postLeft > postRight) return nullptr;

// 1. 后序末元素即为当前根节点
int rootVal = postorder[postRight];
TreeNode* root = new TreeNode(rootVal);

// 2. 在中序序列中定位根节点
int inRootIdx = inorderIndex[rootVal];

// 3. 计算左子树节点数量
int leftSize = inRootIdx – inLeft;

// 4. 递归重建左子树
// 后序左子树范围：[postLeft, postLeft+leftSize-1]
// 中序左子树范围：[inLeft, inRootIdx-1]
root->left = build(postorder,
postLeft, postLeft + leftSize – 1,
inLeft, inRootIdx – 1);

// 5. 递归重建右子树
// 后序右子树范围：[postLeft+leftSize, postRight-1]
// 中序右子树范围：[inRootIdx+1, inRight]
root->right = build(postorder,
postLeft + leftSize, postRight – 1,
inRootIdx + 1, inRight);

return root;
}

public:
TreeNode* buildTree(vector<int>& postorder, vector<int>& inorder) {
int n = postorder.size();
for (int i = 0; i < n; i++) {
inorderIndex[inorder[i]] = i;
}
return build(postorder, 0, n – 1, 0, n – 1);
}
};

3.3 执行过程追踪

递归过程（树形展开）：

build(post[0..4], in[0..4])
rootVal=3, inRootIdx=1, leftSize=1
├─ 左子树 build(post[0..0], in[0..0])
│ rootVal=9
│ return Node(9)
└─ 右子树 build(post[1..3], in[2..4])
rootVal=20, inRootIdx=3, leftSize=1
├─ 左子树 build(post[1..1], in[2..2])
│ return Node(15)
└─ 右子树 build(post[2..2], in[4..4])
return Node(7)
return Node(20)
return Node(3)

递归参数追踪表：

3.4 非递归实现（迭代 + 栈）

后序+中序的迭代方案：将后序序列逆序处理，转化为"根→右→左"的类前序问题。

TreeNode* buildTreeIterative_PostIn(vector<int>& postorder, vector<int>& inorder) {
if (postorder.empty()) return nullptr;

int n = postorder.size();
// 后序末尾为根节点，逆序遍历后序 = 根→右→左
TreeNode* root = new TreeNode(postorder[n – 1]);
stack<TreeNode*> stk;
stk.push(root);

int inIdx = n – 1; // 中序指针从末尾开始

for (int i = n – 2; i >= 0; i—) {
TreeNode* node = stk.top();
TreeNode* child = new TreeNode(postorder[i]);

// 若栈顶节点值 ≠ 中序当前值，说明还在向右走
if (node->val != inorder[inIdx]) {
node->right = child; // 作为右子节点
} else {
// 回溯：找到左子节点应挂载的父节点
while (!stk.empty() && stk.top()->val == inorder[inIdx]) {
node = stk.top();
stk.pop();
inIdx—;
}
node->left = child; // 作为左子节点
}
stk.push(child);
}
return root;
}

3.5 执行过程追踪

以 postorder=[9,15,7,20,3]，inorder=[9,3,15,20,7] 为例：

非递归迭代过程追踪：

迭代算法核心逻辑：逆序遍历后序序列（等价于"根→右→左"），遇到新节点先尝试接到栈顶的右边；若栈顶值等于中序当前值（从末尾往前），说明右子树已完成，回溯找到左子节点的父节点。

后序逆序：[ 3, 20, 7, 15, 9 ] i 从 n-2=3 递减到 0
中序： [ 9, 3, 15, 20, 7 ] inIdx 从 4 开始递减

构建结果验证：

3
/ \\
9 20
/ \\
15 7

节点挂载关系汇总：

四、两种方法对比

4.1 切割规则对比

中序范围的切割规则完全相同，两种方法的本质差异只在于如何从前/后序序列中定位根节点。

4.2 序列切割示意图

前序 + 中序：

前序：[ root | <– leftSize –> | <– rightSize –> ]
preLeft+1 preLeft+leftSize+1
中序：[ <– leftSize –> | root | <– rightSize –> ]
inLeft inRootIdx+1

后序 + 中序：

后序：[ <– leftSize –> | <– rightSize –> | root ]
postLeft postLeft+leftSize postRight
中序：[ <– leftSize –> | root | <– rightSize –> ]
inLeft inRootIdx+1

五、算法复杂度分析

5.1 时间复杂度

⚠️ 若不使用哈希表，每次在中序中线性查找根节点，时间复杂度退化为 O(n²)。

5.2 空间复杂度

5.3 递归 vs 非递归

六、完整可运行代码

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;

// ==================== 节点定义 ====================
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// ==================== 前序 + 中序 → 递归 ====================
class BuildFromPreIn {
unordered_map<int, int> idxMap;

TreeNode* build(const vector<int>& pre, int pL, int pR, int iL, int iR) {
if (pL > pR) return nullptr;
int rootVal = pre[pL];
int inRoot = idxMap[rootVal];
int leftSize = inRoot – iL;
TreeNode* root = new TreeNode(rootVal);
root->left = build(pre, pL + 1, pL + leftSize, iL, inRoot – 1);
root->right = build(pre, pL + leftSize + 1, pR, inRoot + 1, iR);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < (int)inorder.size(); i++)
idxMap[inorder[i]] = i;
return build(preorder, 0, preorder.size()–1, 0, inorder.size()–1);
}
};

// ==================== 前序 + 中序 → 迭代 ====================
TreeNode* buildPreIn_Iter(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) return nullptr;
TreeNode* root = new TreeNode(preorder[0]);
stack<TreeNode*> stk;
stk.push(root);
int inIdx = 0;
for (int i = 1; i < (int)preorder.size(); i++) {
TreeNode* node = stk.top();
TreeNode* child = new TreeNode(preorder[i]);
if (node->val != inorder[inIdx]) {
node->left = child;
} else {
while (!stk.empty() && stk.top()->val == inorder[inIdx]) {
node = stk.top(); stk.pop(); inIdx++;
}
node->right = child;
}
stk.push(child);
}
return root;
}

// ==================== 后序 + 中序 → 递归 ====================
class BuildFromPostIn {
unordered_map<int, int> idxMap;

TreeNode* build(const vector<int>& post, int pL, int pR, int iL, int iR) {
if (pL > pR) return nullptr;
int rootVal = post[pR];
int inRoot = idxMap[rootVal];
int leftSize = inRoot – iL;
TreeNode* root = new TreeNode(rootVal);
root->left = build(post, pL, pL + leftSize – 1, iL, inRoot – 1);
root->right = build(post, pL + leftSize, pR – 1, inRoot + 1, iR);
return root;
}
public:
TreeNode* buildTree(vector<int>& postorder, vector<int>& inorder) {
for (int i = 0; i < (int)inorder.size(); i++)
idxMap[inorder[i]] = i;
return build(postorder, 0, postorder.size()–1, 0, inorder.size()–1);
}
};

// ==================== 后序 + 中序 → 迭代 ====================
TreeNode* buildPostIn_Iter(vector<int>& postorder, vector<int>& inorder) {
if (postorder.empty()) return nullptr;
int n = postorder.size();
TreeNode* root = new TreeNode(postorder[n – 1]);
stack<TreeNode*> stk;
stk.push(root);
int inIdx = n – 1;
for (int i = n – 2; i >= 0; i—) {
TreeNode* node = stk.top();
TreeNode* child = new TreeNode(postorder[i]);
if (node->val != inorder[inIdx]) {
node->right = child;
} else {
while (!stk.empty() && stk.top()->val == inorder[inIdx]) {
node = stk.top(); stk.pop(); inIdx—;
}
node->left = child;
}
stk.push(child);
}
return root;
}

// ==================== 验证：层序打印 ====================
void levelPrint(TreeNode* root, const string& label) {
cout << label << ": [";
if (!root) { cout << "]\\n"; return; }
queue<TreeNode*> q;
q.push(root);
bool first = true;
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (!first) cout << ", ";
cout << node->val;
first = false;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
cout << "]\\n";
}

// ==================== 验证：中序打印 ====================
void inPrint(TreeNode* root, const string& label) {
cout << label << ": [";
stack<TreeNode*> stk;
TreeNode* curr = root;
bool first = true;
while (curr || !stk.empty()) {
while (curr) { stk.push(curr); curr = curr->left; }
curr = stk.top(); stk.pop();
if (!first) cout << ", ";
cout << curr->val;
first = false;
curr = curr->right;
}
cout << "]\\n";
}

int main() {
cout << "====== 测试一：前序 + 中序 ======" << endl;
vector<int> pre1 = {3, 9, 20, 15, 7};
vector<int> in1 = {9, 3, 15, 20, 7};

BuildFromPreIn solverA;
TreeNode* treeA_rec = solverA.buildTree(pre1, in1);
levelPrint(treeA_rec, "递归还原（层序验证）");
inPrint (treeA_rec, "递归还原（中序验证）");

TreeNode* treeA_itr = buildPreIn_Iter(pre1, in1);
levelPrint(treeA_itr, "迭代还原（层序验证）");
inPrint (treeA_itr, "迭代还原（中序验证）");

cout << "\\n====== 测试二：后序 + 中序 ======" << endl;
vector<int> post2 = {9, 15, 7, 20, 3};
vector<int> in2 = {9, 3, 15, 20, 7};

BuildFromPostIn solverB;
TreeNode* treeB_rec = solverB.buildTree(post2, in2);
levelPrint(treeB_rec, "递归还原（层序验证）");
inPrint (treeB_rec, "递归还原（中序验证）");

TreeNode* treeB_itr = buildPostIn_Iter(post2, in2);
levelPrint(treeB_itr, "迭代还原（层序验证）");
inPrint (treeB_itr, "迭代还原（中序验证）");

return 0;
}

预期输出：

====== 测试一：前序 + 中序 ======
递归还原（层序验证）: [3, 9, 20, 15, 7]
递归还原（中序验证）: [9, 3, 15, 20, 7]
迭代还原（层序验证）: [3, 9, 20, 15, 7]
迭代还原（中序验证）: [9, 3, 15, 20, 7]

====== 测试二：后序 + 中序 ======
递归还原（层序验证）: [3, 9, 20, 15, 7]
递归还原（中序验证）: [9, 3, 15, 20, 7]
迭代还原（层序验证）: [3, 9, 20, 15, 7]
迭代还原（中序验证）: [9, 3, 15, 20, 7]

验证方式：对还原后的二叉树做中序遍历，若结果与输入的中序序列完全吻合，则还原正确。