文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载导读本文基于 algorithm-base 仓库《animation-simulation/二叉树》系列讲解二叉树前序遍历的非递归迭代实现。前序遍历的顺序是根 → 左 → 右在刷题与面试中掌握其迭代写法与递归写法同等重要。读完本文你将理解为什么前序遍历要借助栈、为什么要先压右孩子再压左孩子并能独立写出 Java / Swift / Go 三种语言的通过版代码。前序遍历是什么前序遍历的顺序是对于树中的某个节点先遍历该节点本身然后再遍历其左子树最后遍历其右子树。以根节点出发前序遍历的结果序列正是根 → 左子树全部 → 右子树全部。这一顺序也是三种深度优先遍历前序、中序、后序中最直观的一种它是后续学习中序遍历迭代、后序遍历迭代.md)以及MORRIS 前序遍历.md)的基础。对二叉树的基础概念根节点、子树、左右子树次序不熟悉的读者可先阅读二叉树基础。迭代法用栈替代系统递归栈为什么是栈而不是队列回忆二叉树的层序遍历我们借助队列先进先出FIFO完成逐层访问因为层序遍历要求先处理先进入的节点。而前序遍历要求根 → 左 → 右的深度优先顺序访问完当前节点后下一步应该立刻进入它的左子树而不是先访问同层的兄弟节点。这正好对应栈先进后出LIFO的特性所以前序遍历的迭代实现选择栈作为辅助数据结构。关于栈的模型、push / pop 操作与典型应用可参考仓库中的关于栈和队列的那些事一文。入栈顺序先右后左这是整个迭代法最核心、也最容易写反的一步栈的特性是先进后出借助栈完成前序遍历时应当先将右子节点入栈再将左子节点入栈。这样出栈时左子节点会先被弹出处理右子节点随后再被处理从而满足前序遍历先左后右的要求。以二叉树[1, 2, 3]为例1 为根左孩子 2右孩子 3手动模拟一遍root节点 1入栈栈内[1]栈非空弹出 1记录1其右孩子 3 入栈左孩子 2 入栈栈内[3, 2]弹出 2记录22 无孩子弹出 3记录33 无孩子栈空结束。输出序列1 → 2 → 3正确。完整流程总结用一句话概括整个算法当栈不为空时栈顶元素出栈并记录若其右孩子不为空则右孩子入栈若其左孩子不为空则左孩子入栈。注意与层序遍历需要先把根节点放入队列一样迭代前序遍历也需要先将 root 节点入栈再进入 while 循环。复杂度分析时间复杂度O(n)需要对树中所有节点各访问一次空间复杂度O(n)栈的开销。平均情况下为 O(log n)平衡二叉树栈深约为树高最坏情况为 O(n)即斜二叉树所有节点只有左孩子或只有右孩子时栈中需要同时保存接近全部节点。参考代码Javaclass Solution { public ListInteger preorderTraversal(TreeNode root) { ListInteger list new ArrayList(); StackTreeNode stack new Stack(); if (root null) return list; stack.push(root); while (!stack.isEmpty()) { TreeNode temp stack.pop(); if (temp.right ! null) { stack.push(temp.right); } if (temp.left ! null) { stack.push(temp.left); } //这里也可以放到前面 list.add(temp.val); } return list; } }Swiftclass Solution { func preorderTraversal(_ root: TreeNode?) - [Int] { var list:[Int] [] var stack:[TreeNode] [] guard root ! nil else { return list } stack.append(root!) while !stack.isEmpty { let temp stack.popLast() if let right temp?.right { stack.append(right) } if let left temp?.left { stack.append(left) } //这里也可以放到前面 list.append((temp?.val)!) } return list } }Gofunc preorderTraversal(root *TreeNode) []int { res : []int{} if root nil { return res } stk : []*TreeNode{root} for len(stk) ! 0 { temp : stk[len(stk) - 1] stk stk[: len(stk) - 1] if temp.Right ! nil { stk append(stk, temp.Right) } if temp.Left ! nil { stk append(stk, temp.Left) } res append(res, temp.Val) } return res }三个版本的结构完全一致先判空根入栈循环内先取栈顶、后压右左。其中list.add(temp.val)这一步放在出栈后立刻执行即可因为此时temp就是要访问的节点。与系列其他遍历实现的衔接掌握了栈 先右后左这一思想后可以自然衔接本仓库二叉树系列的其他文章二叉树中序遍历迭代同样借助栈但改用指针不断向左孩子移动并入栈指针为空时出栈并把指针指向右孩子的策略与前序遍历的入栈方式形成鲜明对比二叉树的后续遍历迭代.md)需要额外的preNode指针记录上一个访问的节点以判断右子树是否已被访问是三者中实现最复杂的二叉树的前序遍历Morris.md)利用树中大量空闲指针叶子节点的 right将空间复杂度优化到 O(1)可作为迭代法之后进一步学习的进阶话题。小结迭代前序遍历的核心可归纳为三点用栈LIFO而非队列匹配深度优先的根 → 左 → 右顺序先压右孩子、再压左孩子保证出栈次序为先左后右根节点先入栈再进入 while 循环循环内弹出即记录、有孩子则入栈。掌握这份代码后你可以在 LeetCode 144二叉树的前序遍历等题目上直接套用并以此为模板扩展到中序、后序的迭代写法。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐二叉树前序遍历全解递归 DFS、迭代栈与 Morris 遍历LeetCode 144二叉树前序遍历全解递归 DFS、迭代栈与 Morris 遍历LeetCode 144 本文以 LeetCode 144「二叉树的前序遍历」为核心系统讲解示例工程教程3种遍历10行代码动画图解二叉树前序/中序/后序遍历技巧3种遍历10行代码动画图解二叉树前序/中序/后序遍历技巧 你是否还在为二叉树遍历头疼刷题时对着前序、中序、后序遍历手足无措本文通过动画演示极简代码10文档教程知识库algorithm-base 二叉树后序遍历Morris 法详解利用空闲指针实现 O(1) 空间的后序遍历algorithm base 二叉树后序遍历Morris 法详解利用空闲指针实现 O 1 空间的后序遍历 导读 后序遍历left → right → r文档教程知识库上一篇终极免费风扇控制指南FanControl让你的电脑散热更安静高效下一篇华硕笔记本性能调优神器G-Helper轻量级控制工具完全指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考