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

[力扣 105]二叉树前中后序遍历精讲原理、实现与二叉树还原Bilibili 同步视频一、二叉树遍历的整体认知二、前中后序遍历原理深度拆解 前序遍历根 → 左 → 右示例遍历过程 中序遍历左 → 根 → 右示例遍历过程 后序遍历左 → 右 → 根示例遍历过程 遍历核心思想递归三、C代码实现递归与迭代遍历 递归遍历实现1. 前序遍历递归2. 中序遍历递归3. 后序遍历递归 迭代遍历实现1. 前序遍历迭代2. 中序遍历迭代3. 后序遍历迭代双栈法 测试代码 递归与迭代的性能对比四、核心进阶利用遍历结果还原二叉树核心原理 中序前序 还原二叉树详解C实现还原步骤递归C代码实现中序前序还原二叉树 扩展中序后序 还原二叉树五、总结Bilibili 同步视频[力扣 105]二叉树前中后序遍历精讲原理、实现与二叉树还原 二叉树作为数据结构中的核心基础其遍历操作是处理树结构问题的基石。前序、中序、后序遍历作为二叉树最经典的三种遍历方式围绕根节点的访问顺序形成了独特的遍历逻辑更是面试与实际开发中的高频考点。本文将从遍历原理出发结合实例拆解遍历过程通过C代码实现递归与迭代遍历同时讲解如何利用中序前序/后序遍历结果还原二叉树结构让你彻底吃透二叉树遍历的核心逻辑一、二叉树遍历的整体认知首先要明确的是前序、中序、后序并非二叉树唯一的遍历方式还有层序遍历等方式但这三种因基于根节点的访问顺序形成了递归化的遍历逻辑成为处理二叉树问题的核心方法。这三种遍历的核心区分依据根节点在遍历过程中的访问位置。对二叉树的任意子树都遵循左子树和右子树的遍历优先级仅根节点的访问时机不同这也是二叉树遍历能通过递归实现的关键——大问题拆解为子树的小问题子问题解法与原问题完全一致。为了方便后续讲解我们以一棵固定的二叉树为示例所有遍历操作均基于此树展开1 / \ 2 3 / \ \ 4 5 6此树的节点结构为根节点1左子树以2为根包含子节点4、5右子树以3为根包含子节点6。二、前中后序遍历原理深度拆解 前序遍历根 → 左 → 右核心规则先访问根节点再递归前序遍历左子树最后递归前序遍历右子树简称根左右。前序遍历的关键是根节点最先访问子树的遍历仍遵循前序规则。示例遍历过程访问根节点1对左子树根2执行前序遍历访问2 → 访问左子节点4 → 访问右子节点5对右子树根3执行前序遍历访问3 → 访问右子节点6最终遍历结果1 → 2 → 4 → 5 → 3 → 6。 中序遍历左 → 根 → 右核心规则先递归中序遍历左子树再访问根节点最后递归中序遍历右子树简称左根右。中序遍历的关键是根节点夹在左右子树中间这一特性是后续还原二叉树的核心依据。示例遍历过程对左子树根2执行中序遍历访问左子节点4 → 访问根2 → 访问右子节点5访问根节点1对右子树根3执行中序遍历访问根3 → 访问右子节点6最终遍历结果4 → 2 → 5 → 1 → 3 → 6。 后序遍历左 → 右 → 根核心规则先递归后序遍历左子树再递归后序遍历右子树最后访问根节点简称左右根。后序遍历的关键是根节点最后访问常用于二叉树的删除、释放资源等操作先处理子节点再处理父节点。示例遍历过程对左子树根2执行后序遍历访问左子节点4 → 访问右子节点5 → 访问根2对右子树根3执行后序遍历访问右子节点6 → 访问根3访问根节点1最终遍历结果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, vectorint 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, vectorint 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, vectorint res) { if (root nullptr) return; postorderRecur(root-left, res); // 1. 递归遍历左子树 postorderRecur(root-right, res); // 2. 递归遍历右子树 res.push_back(root-val); // 3. 访问根节点 } 迭代遍历实现递归遍历虽简洁但存在函数调用栈开销在数据量较大时性能不如迭代遍历。迭代遍历基于栈stack模拟递归的调用过程核心是手动控制节点的入栈和出栈顺序匹配遍历规则。1. 前序遍历迭代// 前序遍历根左右迭代实现栈 vectorint preorderIter(TreeNode* root) { vectorint res; if (root nullptr) return res; stackTreeNode* 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. 中序遍历迭代// 中序遍历左根右迭代实现栈 vectorint inorderIter(TreeNode* root) { vectorint res; if (root nullptr) return res; stackTreeNode* 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. 后序遍历迭代双栈法后序遍历的迭代实现稍复杂双栈法是最易理解的方式利用两个栈先按根右左遍历再将结果反转得到左右根。// 后序遍历左右根迭代实现双栈法 vectorint postorderIter(TreeNode* root) { vectorint res; if (root nullptr) return res; stackTreeNode* 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(); vectorint 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; } 递归与迭代的性能对比遍历方式递归实现迭代实现代码复杂度低易写易理解较高需手动控制栈时间复杂度O(n)每个节点访问一次O(n)每个节点入栈出栈一次空间复杂度O(n)最坏情况斜树函数调用栈深度为nO(n)栈的存储空间最多为n性能表现存在函数调用开销大数据量下稍慢无函数调用开销性能更优总结入门阶段优先掌握递归实现理解遍历核心逻辑实际开发/面试中需能手写迭代实现尤其是中序遍历并说明递归与迭代的区别。四、核心进阶利用遍历结果还原二叉树 这是二叉树遍历的高频面试题已知中序遍历前序遍历或中序遍历后序遍历的结果还原唯一的二叉树结构注意仅前序后序无法还原唯一二叉树因为无法确定左右子树边界。核心原理还原二叉树的核心仍基于递归思想利用中序和前序/后序的特性拆解问题前序遍历特性第一个节点一定是整棵树的根节点后序遍历特性最后一个节点一定是整棵树的根节点中序遍历特性根节点将中序序列拆分为左子树中序序列和右子树中序序列左、右序列的节点数分别对应左、右子树的节点数。通过上述特性可将“还原整棵树”拆解为“还原左子树”和“还原右子树”直到子树序列为空时终止。 中序前序 还原二叉树详解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_mapint, int inoMap; // 递归还原二叉树参数为前序左右边界、中序左右边界 TreeNode* buildTreeByPreIn(vectorint 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; // 还原左子树前序[preL1, preLleftNum]中序[inL, rootInx-1] root-left buildTreeByPreIn(pre, preL1, preLleftNum, inL); // 还原右子树前序[preLleftNum1, preR]中序[rootInx1, inR] root-right buildTreeByPreIn(pre, preLleftNum1, preR, rootInx1); return root; } // 入口函数 TreeNode* buildTree(vectorint preorder, vectorint 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); } 扩展中序后序 还原二叉树核心逻辑与中序前序一致仅根节点的选取和前序/后序的边界拆分不同后序遍历的最后一个节点为根节点后序序列中最后leftNum个节点为左子树后序序列剩余节点除根节点为右子树后序序列。其代码实现可基于上述思路修改核心递归思想不变。五、总结✨ 二叉树的前序、中序、后序遍历是数据结构的基础也是处理二叉树问题的“万能钥匙”无论是求树的高度、路径和还是还原二叉树都基于遍历的核心逻辑递归拆解子树按规则访问节点。本文的核心知识点梳理前中后序遍历的区分根节点的访问位置分别为根左右、左根右、左右根遍历的实现递归简洁易理解迭代基于栈模拟递归性能更优需熟练手写两种实现二叉树还原仅中序前序/后序可还原唯一二叉树核心是利用遍历特性递归拆解左右子树核心思想递归是二叉树遍历与还原的灵魂大问题拆解为子问题子问题解法与原问题一致。掌握本文的内容不仅能应对面试中的二叉树遍历考题更能为后续学习二叉搜索树、平衡二叉树等高级树结构打下坚实的基础。建议大家手动敲写代码结合示例树调试运行真正吃透遍历的每一个细节附本文所有代码均可直接在C编译器如Dev-C、VS、Clion中运行建议大家修改节点结构和遍历序列自行测试不同二叉树的遍历与还原效果加深理解。