[力扣 105]二叉树前中后序遍历精讲：原理、实现与二叉树还原

Bilibili 同步视频

[力扣 105]二叉树前中后序遍历精讲：原理、实现与二叉树还原

🌳 二叉树作为数据结构中的核心基础，其遍历操作是处理树结构问题的基石。前序、中序、后序遍历作为二叉树最经典的三种遍历方式，围绕根节点的访问顺序形成了独特的遍历逻辑，更是面试与实际开发中的高频考点。本文将从遍历原理出发，结合实例拆解遍历过程，通过C++代码实现递归与迭代遍历，同时讲解如何利用中序+前序/后序遍历结果还原二叉树结构，让你彻底吃透二叉树遍历的核心逻辑！

一、二叉树遍历的整体认知

首先要明确的是，前序、中序、后序并非二叉树唯一的遍历方式，还有层序遍历等方式，但这三种因基于根节点的访问顺序形成了递归化的遍历逻辑，成为处理二叉树问题的核心方法。

这三种遍历的核心区分依据：根节点在遍历过程中的访问位置。

对二叉树的任意子树，都遵循左子树和右子树的遍历优先级，仅根节点的访问时机不同，这也是二叉树遍历能通过递归实现的关键——大问题拆解为子树的小问题，子问题解法与原问题完全一致。

为了方便后续讲解，我们以一棵固定的二叉树为示例，所有遍历操作均基于此树展开：

1 / \ 2 3 / \ \ 4 5 6

此树的节点结构为：根节点1，左子树以2为根（包含子节点4、5），右子树以3为根（包含子节点6）。

二、前中后序遍历原理深度拆解

🔹 前序遍历：根 → 左 → 右

核心规则：先访问根节点，再递归前序遍历左子树，最后递归前序遍历右子树，简称根左右。

前序遍历的关键是根节点最先访问，子树的遍历仍遵循前序规则。

示例遍历过程

1. 访问根节点1；

2. 对左子树（根2）执行前序遍历：访问2 → 访问左子节点4 → 访问右子节点5；

3. 对右子树（根3）执行前序遍历：访问3 → 访问右子节点6；

4. 最终遍历结果：1 → 2 → 4 → 5 → 3 → 6。

🔹 中序遍历：左 → 根 → 右

核心规则：先递归中序遍历左子树，再访问根节点，最后递归中序遍历右子树，简称左根右。

中序遍历的关键是根节点夹在左右子树中间，这一特性是后续还原二叉树的核心依据。

示例遍历过程

1. 对左子树（根2）执行中序遍历：访问左子节点4 → 访问根2 → 访问右子节点5；

2. 访问根节点1；

3. 对右子树（根3）执行中序遍历：访问根3 → 访问右子节点6；

4. 最终遍历结果：4 → 2 → 5 → 1 → 3 → 6。

🔹 后序遍历：左 → 右 → 根

核心规则：先递归后序遍历左子树，再递归后序遍历右子树，最后访问根节点，简称左右根。

后序遍历的关键是根节点最后访问，常用于二叉树的删除、释放资源等操作（先处理子节点，再处理父节点）。

示例遍历过程

1. 对左子树（根2）执行后序遍历：访问左子节点4 → 访问右子节点5 → 访问根2；

2. 对右子树（根3）执行后序遍历：访问右子节点6 → 访问根3；

3. 访问根节点1；

4. 最终遍历结果：4 → 5 → 2 → 6 → 3 → 1。

📌 遍历核心思想：递归

三种遍历的实现均围绕递归思想展开：将整棵树的遍历拆解为根节点访问+左子树遍历+右子树遍历，而左、右子树的遍历又可以继续拆解，直到子树为空节点时终止递归。

递归的天然契合性让二叉树遍历的代码实现极其简洁，这也是入门阶段优先学习递归遍历的原因。

三、C++代码实现：递归与迭代遍历

在实现代码前，我们先定义二叉树的节点结构，这是所有操作的基础：

#include <iostream> #include <vector> #include <stack> using namespace std; // 定义二叉树节点结构 struct TreeNode { int val; // 节点值 TreeNode* left; // 左子节点指针 TreeNode* right;// 右子节点指针 // 构造函数 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

基于上述结构，我们分别实现递归遍历（简洁易理解）和迭代遍历（性能更优，基于栈实现）。

🔧 递归遍历实现

递归遍历的代码完全遵循遍历规则，逻辑与原理高度一致，是入门阶段的首选实现方式。

1. 前序遍历（递归）

// 前序遍历：根左右，递归实现 void preorderRecur(TreeNode* root, vector<int>& res) { if (root == nullptr) return; // 递归终止条件：空节点 res.push_back(root->val); // 1. 访问根节点 preorderRecur(root->left, res); // 2. 递归遍历左子树 preorderRecur(root->right, res); // 3. 递归遍历右子树 }

2. 中序遍历（递归）

// 中序遍历：左根右，递归实现 void inorderRecur(TreeNode* root, vector<int>& res) { if (root == nullptr) return; inorderRecur(root->left, res); // 1. 递归遍历左子树 res.push_back(root->val); // 2. 访问根节点 inorderRecur(root->right, res); // 3. 递归遍历右子树 }

3. 后序遍历（递归）

// 后序遍历：左右根，递归实现 void postorderRecur(TreeNode* root, vector<int>& res) { if (root == nullptr) return; postorderRecur(root->left, res); // 1. 递归遍历左子树 postorderRecur(root->right, res); // 2. 递归遍历右子树 res.push_back(root->val); // 3. 访问根节点 }

🔧 迭代遍历实现

递归遍历虽简洁，但存在函数调用栈开销，在数据量较大时性能不如迭代遍历。迭代遍历基于栈（stack）模拟递归的调用过程，核心是手动控制节点的入栈和出栈顺序，匹配遍历规则。

1. 前序遍历（迭代）

// 前序遍历：根左右，迭代实现（栈） vector<int> preorderIter(TreeNode* root) { vector<int> res; if (root == nullptr) return res; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); res.push_back(node->val); // 访问根节点 // 栈是后进先出，先压右子树，再压左子树，保证左子树先访问 if (node->right != nullptr) st.push(node->right); if (node->left != nullptr) st.push(node->left); } return res; }

2. 中序遍历（迭代）

// 中序遍历：左根右，迭代实现（栈） vector<int> inorderIter(TreeNode* root) { vector<int> res; if (root == nullptr) return res; stack<TreeNode*> st; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { // 先遍历到最左子节点，沿途节点入栈 while (cur != nullptr) { st.push(cur); cur = cur->left; } cur = st.top(); st.pop(); res.push_back(cur->val); // 访问根节点 cur = cur->right; // 遍历右子树 } return res; }

3. 后序遍历（迭代，双栈法）

后序遍历的迭代实现稍复杂，双栈法是最易理解的方式：利用两个栈，先按根右左遍历，再将结果反转得到左右根。

// 后序遍历：左右根，迭代实现（双栈法） vector<int> postorderIter(TreeNode* root) { vector<int> res; if (root == nullptr) return res; stack<TreeNode*> st1, st2; st1.push(root); while (!st1.empty()) { TreeNode* node = st1.top(); st1.pop(); st2.push(node); // 先压左子树，再压右子树，保证st1弹出顺序为右→左 if (node->left != nullptr) st1.push(node->left); if (node->right != nullptr) st1.push(node->right); } // st2中为根→右→左，弹出后反转即为左→右→根 while (!st2.empty()) { res.push_back(st2.top()->val); st2.pop(); } return res; }

🔧 测试代码

将示例二叉树构建后，调用上述遍历函数，验证结果正确性：

// 构建示例二叉树 TreeNode* buildTree() { TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->right = new TreeNode(6); return root; } // 主函数测试 int main() { TreeNode* root = buildTree(); vector<int> res; // 测试递归前序 preorderRecur(root, res); cout << "前序遍历（递归）："; for (int num : res) cout << num << " "; // 1 2 4 5 3 6 cout << endl; // 测试迭代中序 res = inorderIter(root); cout << "中序遍历（迭代）："; for (int num : res) cout << num << " "; // 4 2 5 1 3 6 cout << endl; // 测试迭代后序 res = postorderIter(root); cout << "后序遍历（迭代）："; for (int num : res) cout << num << " "; // 4 5 2 6 3 1 cout << endl; return 0; }

📊 递归与迭代的性能对比

四、核心进阶：利用遍历结果还原二叉树

💡 这是二叉树遍历的高频面试题：已知中序遍历+前序遍历或中序遍历+后序遍历的结果，还原唯一的二叉树结构（注意：仅前序+后序无法还原唯一二叉树，因为无法确定左右子树边界）。

核心原理

还原二叉树的核心仍基于递归思想，利用中序和前序/后序的特性拆解问题：

1. 前序遍历特性：第一个节点一定是整棵树的根节点；

2. 后序遍历特性：最后一个节点一定是整棵树的根节点；

3. 中序遍历特性：根节点将中序序列拆分为左子树中序序列和右子树中序序列，左、右序列的节点数分别对应左、右子树的节点数。

通过上述特性，可将“还原整棵树”拆解为“还原左子树”和“还原右子树”，直到子树序列为空时终止。

🔍 中序+前序 还原二叉树（详解+C++实现）

我们以示例的遍历结果为输入，讲解还原过程：

• 前序遍历结果：[1,2,4,5,3,6]

• 中序遍历结果：[4,2,5,1,3,6]

还原步骤（递归）

步骤1：确定整棵树根节点 前序第一个节点为1 → 整棵树根节点是1； 中序中找到1的位置，将中序拆分为左序列[4,2,5]（左子树）和右序列[3,6]（右子树）。 步骤2：还原左子树 左子树中序序列[4,2,5] → 节点数3； 前序中根节点1后取3个节点[2,4,5] → 左子树前序序列； 前序第一个节点2 → 左子树根节点； 中序中找到2的位置，拆分为左序列[4]和右序列[5]，分别还原2的左、右子树。 步骤3：还原右子树 右子树中序序列[3,6] → 节点数2； 前序中剩余2个节点[3,6] → 右子树前序序列； 前序第一个节点3 → 右子树根节点； 中序中找到3的位置，拆分为左序列[]（空）和右序列[6]，还原3的右子树。 步骤4：递归终止 当子树的中序/前序序列为空时，终止递归，最终还原出原始二叉树。

C++代码实现（中序+前序还原二叉树）

#include <unordered_map> // 利用哈希表快速查找中序序列中节点的索引，避免每次遍历 unordered_map<int, int> inoMap; // 递归还原二叉树：参数为前序左右边界、中序左右边界 TreeNode* buildTreeByPreIn(vector<int>& pre, int preL, int preR, int inL) { if (preL > preR) return nullptr; // 递归终止：前序边界越界 // 前序左边界为当前根节点 int rootVal = pre[preL]; TreeNode* root = new TreeNode(rootVal); // 找到根节点在中序中的索引 int rootInx = inoMap[rootVal]; // 左子树节点数 int leftNum = rootInx - inL; // 还原左子树：前序[preL+1, preL+leftNum]，中序[inL, rootInx-1] root->left = buildTreeByPreIn(pre, preL+1, preL+leftNum, inL); // 还原右子树：前序[preL+leftNum+1, preR]，中序[rootInx+1, inR] root->right = buildTreeByPreIn(pre, preL+leftNum+1, preR, rootInx+1); return root; } // 入口函数 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { // 构建中序节点-索引的哈希表 for (int i = 0; i < inorder.size(); i++) { inoMap[inorder[i]] = i; } // 前序边界[0, preorder.size()-1]，中序左边界0 return buildTreeByPreIn(preorder, 0, preorder.size()-1, 0); }

📌 扩展：中序+后序 还原二叉树

核心逻辑与中序+前序一致，仅根节点的选取和前序/后序的边界拆分不同：

1. 后序遍历的最后一个节点为根节点；

2. 后序序列中，最后leftNum个节点为左子树后序序列，剩余节点（除根节点）为右子树后序序列。

其代码实现可基于上述思路修改，核心递归思想不变。

五、总结

✨ 二叉树的前序、中序、后序遍历是数据结构的基础，也是处理二叉树问题的“万能钥匙”，无论是求树的高度、路径和，还是还原二叉树，都基于遍历的核心逻辑：递归拆解子树，按规则访问节点。

本文的核心知识点梳理：

1. 前中后序遍历的区分：根节点的访问位置，分别为根左右、左根右、左右根；

2. 遍历的实现：递归简洁易理解，迭代基于栈模拟递归，性能更优，需熟练手写两种实现；

3. 二叉树还原：仅中序+前序/后序可还原唯一二叉树，核心是利用遍历特性递归拆解左右子树；

4. 核心思想：递归是二叉树遍历与还原的灵魂，大问题拆解为子问题，子问题解法与原问题一致。

掌握本文的内容，不仅能应对面试中的二叉树遍历考题，更能为后续学习二叉搜索树、平衡二叉树等高级树结构打下坚实的基础。建议大家手动敲写代码，结合示例树调试运行，真正吃透遍历的每一个细节！

附：本文所有代码均可直接在C++编译器（如Dev-C++、VS、Clion）中运行，建议大家修改节点结构和遍历序列，自行测试不同二叉树的遍历与还原效果，加深理解。