二叉树前序、中序、后序遍历：场景选型+算法题实战指南

二叉树前序、中序、后序遍历场景选型算法题实战指南二叉树遍历是算法入门的核心知识点也是笔试、面试的高频考点。很多同学能熟练默写递归、迭代版的遍历代码却在做题时纠结这道题到底该用前序、中序还是后序其实三种遍历的本质区别在于根节点的访问时机而不同的访问时机决定了它们适配的业务场景和算法题型。本文会从「遍历原理→核心差异→适用场景→真题实战」四个维度彻底讲透三种遍历的选型逻辑帮你告别盲目刷题。一、先搞懂三种遍历的核心定义与访问顺序二叉树遍历的核心是按规则访问树中每个节点且仅访问一次对于任意一棵二叉树节点分为根节点Root、左子树Left、右子树Right三种遍历的命名就源于根节点的访问顺序前序遍历Pre-order根节点 → 左子树 → 右子树根左右中序遍历In-order左子树 → 根节点 → 右子树左根右后序遍历Post-order左子树 → 右子树 → 根节点左右根举个直观例子对于简单二叉树根(A)→左(B)→右(C)三种遍历结果分别是前序A → B → C中序B → A → C后序B → C → A递归实现是最易懂的写法这里贴极简模板方便后续结合场景理解# 二叉树节点定义classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightright# 前序遍历defpreorder(root,res):ifnotroot:returnres.append(root.val)# 先访问根preorder(root.left,res)preorder(root.right,res)# 中序遍历definorder(root,res):ifnotroot:returninorder(root.left,res)res.append(root.val)# 中间访问根inorder(root.right,res)# 后序遍历defpostorder(root,res):ifnotroot:returnpostorder(root.left,res)postorder(root.right,res)res.append(root.val)# 最后访问根关键结论前序是自上而下的访问逻辑后序是自下而上的访问逻辑中序则是有序遍历的专属逻辑这是选型的核心依据二、前序遍历自上而下先处理根再扩散2.1 核心特性先访问根节点再递归处理左右子树属于自上而下的扩散式遍历。适合需要先获取父节点信息再处理子节点的场景子节点的逻辑依赖父节点的状态/结果。2.2 典型适用场景场景1二叉树的复制/克隆想要克隆一棵二叉树必须先创建根节点再递归创建左右子树子节点依赖父节点先创建前序遍历完美适配。场景2前缀表达式求值/二叉树序列化二叉树序列化是将树结构转为字符串前序序列化能保留「根-左-右」的结构反序列化时可快速还原前缀表达式波兰式的计算逻辑也是先算运算符再算左右操作数和前序遍历一致。场景3路径搜索/根到节点的路径获取查找从根节点到目标节点的路径时需要先记录当前根节点再深入左右子树一旦找到目标立即回溯前序遍历能保证路径按「根→子节点」顺序记录。场景4树的前序构造/重建二叉树已知前序中序遍历序列重建二叉树时前序遍历的第一个元素就是根节点可快速定位根拆分左右子树。场景5自上而下的树修改/标记比如给二叉树每个节点赋值父节点指针、翻转二叉树部分场景、树的深度标记自上而下传递深度值等。2.3 算法真题实战例题LeetCode 144. 二叉树的前序遍历、LeetCode 297. 二叉树的序列化与反序列化、LeetCode 257. 二叉树的所有路径实战思路二叉树所有路径前序遍历每进入一个节点就将其加入路径到达叶子节点时保存路径回溯时移除当前节点全程依赖父节点先入路径的逻辑。三、中序遍历有序专属二叉搜索树必杀技3.1 核心特性左子树→根→右子树的访问顺序天生适配二叉搜索树BST的有序性。对于二叉搜索树中序遍历结果一定是严格递增或递减的有序序列这是中序遍历最核心的价值。3.2 典型适用场景场景1二叉搜索树的合法性校验判断一棵树是否为BST只需中序遍历得到序列检查是否严格递增即可这是最直观、最常用的解法。场景2BST的查找/排序/第k大/第k小元素BST中找第k小元素中序遍历的第k个节点就是答案找有序序列、查找目标值中序遍历都能高效实现。场景3BST的修复/转换比如BST中两个节点被错误交换通过中序遍历找到逆序节点即可修复将BST转为有序链表、累加树也依赖中序的有序性。场景4表达式树的中缀表达式还原表达式树的中序遍历结果就是我们日常书写的中缀表达式符合人类阅读习惯。注意普通二叉树的中序遍历无特殊有序性仅二叉搜索树的中序遍历具备有序性这是中序遍历最核心的应用前提3.3 算法真题实战例题LeetCode 94. 二叉树的中序遍历、LeetCode 98. 验证二叉搜索树、LeetCode 230. 二叉搜索树中第K小的元素实战思路验证BST中序遍历过程中记录前驱节点每次访问当前节点时判断是否大于前驱节点全程满足则为合法BST无需存储完整序列空间复杂度更低。四、后序遍历自下而上先处理子再汇总4.1 核心特性先处理左右子树最后访问根节点属于自下而上的汇总式遍历。适合需要先获取子节点结果再计算父节点的场景父节点的逻辑依赖子节点的状态/结果。4.2 典型适用场景场景1二叉树的删除/销毁删除二叉树时必须先删除左右子节点再删除根节点避免内存泄漏后序遍历的「先子后根」逻辑完全匹配。场景2树的后续求值/汇总计算比如计算二叉树的最大深度、最小深度、路径和、节点个数都需要先获取左右子树的结果再汇总到根节点。场景3后缀表达式求值/后续构造后缀表达式逆波兰式的计算逻辑是先算左右操作数再算运算符和后序遍历一致已知后序中序序列重建二叉树也依赖后序最后一个元素为根节点的特性。场景4树的回溯/子树判断判断一棵二叉树是否为另一棵树的子树、查找最大BST子树、计算子树和都需要先遍历完子树再判断根节点的状态。场景5自底向上的树修改比如将二叉树转为链表、合并二叉树、计算树的直径都需要先处理子节点再更新父节点。4.3 算法真题实战例题LeetCode 145. 二叉树的后序遍历、LeetCode 104. 二叉树的最大深度、LeetCode 110. 平衡二叉树、LeetCode 543. 二叉树的直径实战思路平衡二叉树后序遍历计算每个节点的左右子树高度判断高度差是否≤1同时返回子树高度一旦发现不平衡立即返回结果避免冗余遍历。五、快速选型口诀场景对照表5.1 记忆口诀前序先根自上而下复制序列化全靠它中序有序专搞BST查找排序最丝滑后序先子后汇总深度删除全靠它。5.2 场景速查表遍历方式访问顺序核心逻辑高频算法场景前序遍历根→左→右自上而下父先子后树复制、序列化、根路径、前序构造中序遍历左→根→右有序遍历BST专属BST校验、第k小、有序转换、中缀表达式后序遍历左→右→根自下而上子先父后树深度、平衡判断、删除、子树求和六、进阶思考迭代遍历的场景适配递归遍历代码简洁但存在栈溢出风险树深度过大时笔试面试常要求写迭代版。迭代遍历的场景选型和递归完全一致只是实现方式不同前序迭代用栈模拟先压右节点再压左节点保证出栈顺序为根左右中序迭代用栈一路向左遍历出栈时访问节点再处理右子树后序迭代可通过前序遍历反转根→右→左 → 反转→左→右→根或用标记栈记录节点访问状态迭代版的核心还是贴合遍历顺序的访问逻辑场景选型无需改变。七、总结三种遍历没有优劣之分场景决定选型遇到二叉搜索树相关优先选中序遍历遇到自上而下、先父后子的操作优先选前序遍历遇到自下而上、先子后父的汇总计算优先选后序遍历。刷题时先分析题目需求是要有序序列还是要先处理父节点还是要汇总子节点结果找准核心逻辑遍历方式自然水到渠成。