企业官网建设流程全解析

前言

二叉树的遍历序列问题通常有两类：给定一棵树，求它的前序、中序、后序、层序序列；或者反过来，给定两种遍历序列，重建出唯一的二叉树。前者是遍历，后者是还原，二者共享同一套「根在哪里、左右子树如何划分」的思路。

最常见的误解是「任意两种遍历序列都能唯一确定一棵二叉树」。事实并非如此：前序 + 中序可以，后序 + 中序可以，但前序 + 后序不能。例如前序1, 2、后序2, 1，既可能是「1 的左孩子是 2」，也可能是「1 的右孩子是 2」，两种树的前序和后序完全相同。另一个误解是忽略「节点值互不相同」这个前提：序列里有重复值时，中序里定位根会出现多个候选，划分不再唯一。

本文以 C++17 为准，先梳理四种遍历的定义与唯一性，再实现「前序 + 中序」「后序 + 中序」两种重建，最后给出四种遍历的输出与层序遍历。代码用std::unique_ptr管理节点，避免手动delete。

一、四种遍历与唯一性

唯一性结论：

• 
  
• 前序 + 中序：前序第一个是根，在中序中找到它，左边是左子树、右边是右子树，递归即得唯一树。
• 
  
• 后序 + 中序：后序最后一个是根，其余同理。
• 
  
• 前序 + 后序：只能确定根，无法区分「只有左子树」和「只有右子树」，不唯一。
• 
  
• 层序 + 中序：可以唯一确定，但划分逻辑比前两种复杂，本文不展开。
• 
  

前两种方法的共同前提是节点值互不相同。若有重复值，中序里可能出现多个相同值，无法判断哪个才是根，必须借助额外的位置信息或约定。

二、由前序 + 中序重建

设前序区间为[pl, pr)、中序区间为[il, ir)，长度相等。步骤：

1. 
   
2. 前序的第一个元素pre[pl]是当前子树的根。
3. 
   
4. 在中序中找到该根的位置k。
5. 
   
6. 左子树大小leftLen = k - il。
7. 
   
8. 左子树的前序区间是[pl+1, pl+1+leftLen)，中序区间是[il, k)。
9. 
   
10. 右子树的前序区间是[pl+1+leftLen, pr)，中序区间是[k+1, ir)。
11. 
    
12. 递归构造左右子树。
13. 
    

为了避免每次线性扫描中序数组，先用std::unordered_map<int, std::size_t>记录每个值在中序中的下标，查找降为平均O(1)。

// 适用于 C++17
#include <cstddef>
#include <memory>
#include <unordered_map>
#include <vector>

struct Node {
int val;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
explicit Node(int v) : val(v) {}
};

using Index = std::unordered_map<int, std::size_t>;

std::unique_ptr<Node> buildPreIn(const std::vector<int>& pre, std::size_t pl, std::size_t pr,
const std::vector<int>& in, std::size_t il, std::size_t ir,
const Index& pos) {
if (pl >= pr || il >= ir) return nullptr;

const int rootVal = pre[pl];
const std::size_t k = pos.at(rootVal); // 根在中序中的位置
const std::size_t leftLen = k - il;

auto root = std::make_unique<Node>(rootVal);
root->left = buildPreIn(pre, pl + 1, pl + 1 + leftLen, in, il, k, pos);
root->right = buildPreIn(pre, pl + 1 + leftLen, pr, in, k + 1, ir, pos);
return root;
}

std::unique_ptr<Node> buildFromPreIn(const std::vector<int>& pre,
const std::vector<int>& in) {
if (pre.size() != in.size() || pre.empty()) return nullptr;
Index pos;
pos.reserve(in.size());
for (std::size_t i = 0; i < in.size(); ++i) {
pos[in[i]] = i;
}
return buildPreIn(pre, 0, pre.size(), in, 0, in.size(), pos);
}

以pre = {3, 9, 20, 15, 7}、in = {9, 3, 15, 20, 7}为例推演：根是 3，在中序中下标为 1，左子树大小 1。左子树前序{9}、中序{9}；右子树前序{20, 15, 7}、中序{15, 20, 7}，根为 20，左子 15、右子 7。最终树为 3 的左孩子 9，右孩子 20，20 的左右孩子分别是 15 和 7。

三、由后序 + 中序重建

后序的根在区间末尾，其余划分与前序一致，只是左右子树的区间边界要相应调整：

// 适用于 C++17
std::unique_ptr<Node> buildPostIn(const std::vector<int>& post, std::size_t pl, std::size_t pr,
const std::vector<int>& in, std::size_t il, std::size_t ir,
const Index& pos) {
if (pl >= pr || il >= ir) return nullptr;

const int rootVal = post[pr - 1]; // 后序最后一个才是根
const std::size_t k = pos.at(rootVal);
const std::size_t leftLen = k - il;

auto root = std::make_unique<Node>(rootVal);
root->left = buildPostIn(post, pl, pl + leftLen, in, il, k, pos);
root->right = buildPostIn(post, pl + leftLen, pr - 1, in, k + 1, ir, pos);
return root;
}

左子树的后序区间是[pl, pl+leftLen)，右子树是[pl+leftLen, pr-1)，注意右子树要把最后那个根排除掉，所以上界是pr - 1而不是pr。这是后序版本与前序版本唯一的结构差异。

四、四种遍历的输出、复杂度与边界

// 适用于 C++17
#include <iostream>
#include <queue>

void preorder(const Node* node, std::vector<int>& out) {
if (node == nullptr) return;
out.push_back(node->val);
preorder(node->left.get(), out);
preorder(node->right.get(), out);
}

void inorder(const Node* node, std::vector<int>& out) {
if (node == nullptr) return;
inorder(node->left.get(), out);
out.push_back(node->val);
inorder(node->right.get(), out);
}

void postorder(const Node* node, std::vector<int>& out) {
if (node == nullptr) return;
postorder(node->left.get(), out);
postorder(node->right.get(), out);
out.push_back(node->val);
}

std::vector<std::vector<int>> levelOrder(const Node* root) {
std::vector<std::vector<int>> result;
if (root == nullptr) return result;

std::queue<const Node*> q;
q.push(root);
while (!q.empty()) {
const std::size_t width = q.size(); // 当前层的节点数
std::vector<int> level;
level.reserve(width);
for (std::size_t i = 0; i < width; ++i) {
const Node* cur = q.front();
q.pop();
level.push_back(cur->val);
if (cur->left) q.push(cur->left.get());
if (cur->right) q.push(cur->right.get());
}
result.push_back(std::move(level));
}
return result;
}

void print(const std::vector<int>& v) {
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}

int main() {
const std::vector<int> pre{3, 9, 20, 15, 7};
const std::vector<int> in{9, 3, 15, 20, 7};

auto root = buildFromPreIn(pre, in);
std::vector<int> seq;

preorder(root.get(), seq); print(seq);
seq.clear();
inorder(root.get(), seq); print(seq);
seq.clear();
postorder(root.get(), seq); print(seq);

for (const auto& level : levelOrder(root.get())) {
print(level);
}
return 0;
}

层序遍历用队列实现，width = q.size()在进入内层循环前固定，保证一次只处理一层。若把q.size()直接写在for条件里，队列在循环中增长，条件会随之变化，层边界就乱了。

复杂度与边界

用哈希表记录中序下标后，重建的时间复杂度是O(n)（平均），空间复杂度是O(n)，其中n是节点数。递归深度等于树高h：平衡树是O(log n)，链状树退化为O(n)，极端情况下可能栈溢出。

边界情况：

• 
  
• 空序列：pre.size() != in.size()或pre.empty()时返回nullptr。
• 
  
• 单节点：前序与中序都是{x}，构造一个叶子。
• 
  
• 只有左子树或只有右子树：leftLen为 0 或等于区间长度，递归的一侧为空，另一侧继续。
• 
  
• 两序列长度不等：属于非法输入，直接返回nullptr，不要越界访问。
• 
  

常见坑点

1. 认为前序 + 后序能唯一建树

❌ 用前序和后序直接划分左右子树，得到一棵「看似合理」的树。 ✅ 明确前序 + 后序不唯一；需要唯一结果时要求提供中序或层序。

2. 忽略重复值

❌ 节点值可以重复，仍用unordered_map记录「值到下标」的映射。 ✅ 先确认题目保证值互不相同；否则需要用「值 + 出现序号」或直接线性扫描配合区间约束。

3. 区间边界写错

❌ 前序左子树写成[pl+1, pl+leftLen]，把右子树的第一个元素也包含进来。 ✅ 半开区间[pl+1, pl+1+leftLen)，长度恰好是leftLen。

4. 后序根的位置取错

❌rootVal = post[pl]，把后序第一个当成根。 ✅ 后序的根是post[pr - 1]，右子树递归上界是pr - 1。

5. 中序下标没有减偏移

❌leftLen = k，忽略了中序区间起点il不一定为 0。 ✅leftLen = k - il，始终用相对当前区间的长度。

6. 层序遍历层边界混乱

❌while (!q.empty()) { ... for (std::size_t i = 0; i < q.size(); ++i) ... }，q.size()随入队变化。 ✅ 进入内层前保存width = q.size()。

7. 用裸指针管理节点

❌Node* root = new Node(...)，异常或提前返回时泄漏。 ✅ 用std::unique_ptr<Node>，父子所有权清晰。

8. 递归深度失控

❌ 对链状树（每个节点只有右孩子）递归建树，深度等于节点数。 ✅ 评估输入规模；必要时改用显式栈的迭代建树。

总结

遍历序列问题的核心是「用根的位置切分区间」。前序根在前、后序根在后、中序根在中间，三者一组合就能确定子树范围。写代码时把区间定义成半开、把长度算成k - il、把哈希表当作加速手段而非正确性前提，重建逻辑就不会在边界上出错。