二叉树后序遍历迭代法详解：栈 + preNode 指针实现（algorithm-base 动画图解）

文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载后序遍历是二叉树三种深度优先遍历中最难用迭代实现的一种其难点在于当某个节点从栈中弹出时我们无法仅凭节点自身判断它的右子树是否已经被访问过。本文以 algorithm-base 仓库中「二叉树后序遍历迭代」一文为主体完整讲解借助栈与preNode指针实现后序遍历的思路、动画拆解、三种语言的完整代码Java / Swift / Go、pop与peek两种写法变体并与仓库中前序、中序的迭代实现做横向对比帮助读者彻底吃透二叉树非递归遍历的通用套路。一、回顾后序遍历的顺序与递归实现在开始迭代法之前先复习一下后序遍历的定义对于树中的某个节点先遍历该节点的左子树再遍历其右子树最后遍历该节点。也就是说访问顺序是「左 - 右 - 根」与前序遍历的「根 - 左 - 右」、中序遍历的「左 - 根 - 右」正好对应。关于二叉树的基础概念、节点结构val、left、right三个字段以及四种遍历方式的整体介绍可以参考仓库中的 二叉树基础 一文其中给出了后序遍历的递归版实现对应 LeetCode 145. 二叉树的后序遍历class Solution { public ListInteger postorderTraversal(TreeNode root) { ListInteger res new ArrayList(); postorder(root,res); return res; } public void postorder(TreeNode root, ListInteger res) { if (root null) { return; } postorder(root.left, res); postorder(root.right, res); res.add(root.val); } }递归版的逻辑非常直观先递归左子树再递归右子树最后把根节点的值加入结果。但递归在树很深如斜二叉树时会产生 O(n) 的调用栈开销并且面试中常常要求不用递归实现因此迭代版是必须掌握的能力。二、为什么后序遍历的迭代法更难前序遍历的迭代版借助栈利用栈的先进后出特性先让右子节点入栈、再让左子节点入栈出栈时自然先访问左再访问右实现非常简单见 二叉树的前序遍历(栈).md)。中序遍历的迭代版同样借助栈核心是两件事指针不断向节点的左孩子移动沿途执行入栈操作直到找到当前需要遍历的节点当指针为空时开始出栈将指针指向出栈节点的右孩子。详见 二叉树中序遍历迭代。而后序遍历的迭代法相比前两种方法理解上要难一些。原因是前序和中序遍历中节点从栈中弹出时即可立即访问而后序遍历要求左右子树都访问完之后才能访问根节点。当指针从栈中弹出一个节点时我们无法确定它的右子树是否已经被访问完毕——如果右子树还没访问就不能立即输出该节点必须先转向右子树。这就是后序遍历迭代法的核心矛盾如何判断某个节点的右子树是否已经访问过三、核心思路preNode 指针定位上一个访问节点解决上述矛盾的钥匙就是引入一个额外的指针preNode在原文档的动画中表现为橙色箭头/指针用来记录上一个已经被访问过的节点。结合动画过程原文档配有两段动画一段是后序遍历的完整演示一段是迭代过程的逐步模拟我们带着下面两个问题去看动画动画中的橙色指针发挥了什么作用为什么动画中的某个节点出栈之后又入栈了呢看完动画后两个问题的答案也就呼之欲出了问题一橙色指针的作用是什么橙色指针preNode用来定位住上一个访问节点。这样我们就知道当前cur节点的right节点是否被访问如果cur.right preNode说明右子树已经遍历完毕此时才能输出cur节点的值否则说明右子树尚未访问需要继续深入。问题二为什么有的节点出栈后又入栈了呢出栈又入栈的原因是我们发现cur节点的right不为null并且cur.right也还没有被访问过即cur.right ! preNode。因为此时还不能遍历该节点应该先去遍历它右子树中的节点所以将其重新压回栈中然后执行cur cur.right继续处理右子树。也就是说这个算法的完整流程是一直沿左子树深入把所有左孩子压入栈这部分与中序遍历迭代版完全一致弹出栈顶元素作为当前cur判断若cur.right null没有右子树或cur.right preNode右子树已访问完则说明左右子树均已处理完毕此时输出cur.val并更新preNode cur同时令cur null防止下一次循环再次把该节点压栈否则说明右子树还没访问把cur重新压回栈令cur cur.right进入右子树的处理。四、代码实现与逐行剖析4.1 Java 实现LeetCode 145 标准解class Solution { public ListInteger postorderTraversal(TreeNode root) { StackTreeNode stack new Stack(); ListInteger list new ArrayList(); TreeNode cur root; // 这个用来记录前一个访问的节点也就是橙色箭头 TreeNode preNode null; while (cur ! null || !stack.isEmpty()) { // 和之前写的中序一致 while (cur ! null) { stack.push(cur); cur cur.left; } // 1.出栈可以想一下这一步的原因。 cur stack.pop(); // 2.if 里的判断语句有什么含义 if (cur.right null || cur.right preNode) { list.add(cur.val); // 更新下 preNode也就是定位住上一个访问节点。 preNode cur; cur null; } else { // 3.再次压入栈和上面那条 1 的关系 stack.push(cur); cur cur.right; } } return list; } }逐行解读这段代码中的三个关键点while (cur ! null)内层循环与中序遍历一致不断把左孩子压栈直到cur为空。此时栈顶就是最左边、尚未处理的节点。cur stack.pop()先弹出栈顶节点注意此时只是候选节点未必能立即输出。if (cur.right null || cur.right preNode)这是整个算法的灵魂判断。两个条件分别是没有右子树和右子树已被访问只要满足其一就说明该节点的左右子树都处理完了可以输出并更新preNode同时把cur置为null让外层循环回到继续出栈的状态。else分支右子树尚未访问把节点压回栈cur cur.right转向右子树——这就是出栈后又入栈的原因。外层循环条件cur ! null || !stack.isEmpty()保证了当转向右子树后cur非空或者栈中还有待处理节点时循环都将继续直到整棵树处理完毕。4.2 Swift 实现class Solution { func postorderTraversal(_ root: TreeNode?) - [Int] { var list:[Int] [] var stack:[TreeNode] [] var cur root, preNode: TreeNode? while !stack.isEmpty || cur ! nil { //和之前写的中序一致 while cur ! nil { stack.append(cur!) cur cur!.left } //1.出栈可以想一下这一步的原因。 cur stack.popLast() //2.if 里的判断语句有什么含义 if cur!.right nil || cur!.right preNode { list.append(cur!.val) //更新下 preNode也就是定位住上一个访问节点。 preNode cur cur nil } else { //3.再次压入栈和上面那条 1 的关系 stack.append(cur!) cur cur!.right } } return list } }Swift 版本与 Java 版本一一对应只是把Stack换成了数组[TreeNode]入栈用append、出栈用popLast()。注意这里判断引用相等用的是身份运算符比较两个引用是否指向同一个对象而不是值比较这正是preNode指针语义的正确体现。4.3 Go 实现peek 写法func postorderTraversal(root *TreeNode) []int { res : []int{} if root nil { return res } stk : []*TreeNode{} cur : root var pre *TreeNode for len(stk) ! 0 || cur ! nil { for cur ! nil { stk append(stk, cur) cur cur.Left } // 这里符合本文最后的说法使用先获取栈顶元素但是不弹出根据栈顶元素的情况进行响应的处理。 temp : stk[len(stk) - 1] if temp.Right nil || temp.Right pre { stk stk[: len(stk) - 1] res append(res, temp.Val) pre temp } else { cur temp.Right } } return res }注意一个有意思的细节Go 版本没有像 Java / Swift 那样先pop再决定是否压回而是直接使用temp : stk[len(stk) - 1]只读取栈顶元素但不弹出然后根据栈顶节点的右子树状态决定右子树为空或已访问真正执行出栈stk stk[: len(stk) - 1]、输出并更新pre否则不弹出直接cur temp.Right转向右子树。这就是下面要讲的peek写法。两种写法本质上完全等价只是弹出再压回与只看不弹的实现差异。五、写法变体pop 与 peek原文档明确指出也可以修改下代码逻辑将cur stack.pop()改成cur stack.peek()下面再修改一两行代码也可以实现。文档中这样写先pop再按需push回去是为了方便动画模拟大家可以随意发挥。两种写法的对比如下写法操作方式代码特征优劣pop写法先弹出栈顶若右子树未访问则重新压回Java / Swift 版本逻辑集中在一处与动画演示过程一致便于理解peek写法只看栈顶右子树未访问就不弹出直接转向右孩子Go 版本少了一次多余的入栈操作栈状态更干净在工程实践中peek写法Go 版通常更受推荐因为它避免了弹出去又放回来的冗余动作而在教学和动画演示中pop写法Java 版更直观。两者都值得掌握面试时无论写出哪一种都是正确的。六、复杂度分析时间复杂度O(n)其中 n 为二叉树节点总数。每个节点至多被压栈、出栈各一次pop写法中部分节点会被压回一次但仍是常数次总操作次数与节点数呈线性关系。空间复杂度O(n)最坏情况是斜二叉树所有节点只有左子树或只有右子树此时栈中需要同时保存 n 个节点平均情况下为 O(logn)与递归版的空间开销在同一数量级。这一点与前序遍历迭代版的空间复杂度分析一致可参考 二叉树的前序遍历(栈).md)。需要说明的是如果要求空间复杂度优化到 O(1)则需要使用 Morris 遍历法仓库中已有配套文章 二叉树的后续遍历Morris 进行专门讲解。Morris 方法的核心思想是利用节点右孩子中的空闲指针线索实现空间复用在后序遍历中它通过把某节点右子节点路径看成一条链表进行反转遍历来完成输出时间复杂度 O(n)、空间复杂度 O(1)。七、与前序、中序遍历迭代法对比总结把仓库中三篇迭代遍历文章放在一起看会发现三种遍历的迭代实现大同小异可以总结出如下规律遍历方式核心数据结构与前一个节点的关系访问时机前序遍历栈先压右、再压左无需记录节点出栈时立即访问中序遍历栈沿左子树压栈无需记录节点出栈时立即访问后序遍历栈 preNode指针必须知道右子树是否已访问右子树为空或已访问时才输出从代码结构上看后序遍历的迭代版与中序遍历迭代版几乎只有一处关键差异中序在cur stack.pop()之后直接list.add(cur.val)并cur cur.right而后序则在弹出后多了一个if判断用preNode决定是输出还是重新入栈并转向右子树。掌握规律远比死记代码重要前序遍历是入栈时访问中序遍历是出栈时访问后序遍历是出栈时先判断右子树是否访问完再决定是否访问。理解了这条主线即使面试时忘了模板也能现场推导出来。正如原文档所建议的掌握之后建议大家自己手撕一遍从搭建二叉树开始完整地走一遍三种迭代遍历。八、配套练习与仓库导航本篇文章讲解的迭代法可直接用于解决LeetCode 145. 二叉树的后序遍历题目描述与递归版解法见 二叉树基础。如果想系统学完二叉树遍历的完整知识体系建议按以下顺序阅读仓库中的系列文章二叉树基础树与二叉树定义、特殊二叉树、存储方式、四种遍历的递归实现二叉树的前序遍历(栈).md)前序遍历迭代法先压右、再压左二叉树的前序遍历(Morris).md)前序遍历的 O(1) 空间解法二叉树中序遍历迭代中序遍历迭代法沿左子树压栈 出栈转向右孩子二叉树中序遍历Morris中序遍历的 O(1) 空间解法本文后序遍历迭代法栈 preNode指针定位上一个访问节点二叉树的后续遍历Morris后序遍历的 O(1) 空间解法将右子节点路径看作链表进行反转遍历。至此二叉树前序、中序、后序三种遍历方式的迭代法就全部介绍完毕了。三种遍历的迭代实现可以相互印证、对比记忆建议读者在理解本文preNode指针思想的基础上把三种遍历的代码放在一起对比阅读并在 LeetCode 上动手验证真正把这些模板内化为自己的解题能力。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐二叉树前序遍历的栈实现从先进后出到迭代遍历algorithm-base 动画图解系列二叉树前序遍历的栈实现从先进后出到迭代遍历algorithm base 动画图解系列 导读 本文基于 algorithm base 仓库《animatio文档教程知识库algorithm-base 二叉树后序遍历Morris 法详解利用空闲指针实现 O(1) 空间的后序遍历algorithm base 二叉树后序遍历Morris 法详解利用空闲指针实现 O 1 空间的后序遍历 导读 后序遍历left → right → r文档教程知识库algorithm-base 二叉树中序遍历 Morris 算法详解从递归、迭代到 O(1) 空间遍历algorithm base 二叉树中序遍历 Morris 算法详解从递归、迭代到 O 1 空间遍历 导读 本篇基于 algorithm base 仓库 二叉文档教程知识库上一篇Transformers 语音识别指南Whisper 转写 5 分钟跑通下一篇symfony/translation版本路线图社区反馈与功能规划创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考