个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言我们在前面提到了递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。摘要本文介绍了使用栈实现二叉树三种遍历方式的迭代算法。前序遍历通过根→右→左的入栈顺序实现中序遍历需要指针辅助先一路向左压栈再处理节点后序遍历采用根→右→左顺序处理后反转结果。三种方法对比前序遍历访问与处理顺序一致无需指针中序遍历需要指针跟踪未处理节点后序遍历通过反转前序变体实现。这些方法通过显式栈替代递归隐式栈均能达到O(n)时间复杂度是面试常考的二叉树遍历实现方案。前序遍历根 → 左 → 右思路访问和处理顺序一致先根节点 → 再左 → 再右。用栈来模拟递归先压右孩子再压左孩子这样出栈时先左后右。步骤根节点入栈。循环直到栈为空弹出栈顶 → 处理加入结果。右孩子非空 → 入栈。左孩子非空 → 入栈。java public ListInteger preorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) return result; StackTreeNode stack new Stack(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); result.add(node.val); // 中 if (node.right ! null) stack.push(node.right); // 右 if (node.left ! null) stack.push(node.left); // 左 } return result; }二、中序遍历左 → 根 → 右为了解释清楚我说明一下 刚刚在迭代的过程中其实我们有两个操作处理将元素放进result数组中访问遍历节点分析一下为什么刚刚写的前序遍历的代码不能和中序遍历通用呢因为前序遍历的顺序是中左右先访问的元素是中间节点要处理的元素也是中间节点所以刚刚才能写出相对简洁的代码因为要访问的元素和要处理的元素顺序是一致的都是中间节点。那么再看看中序遍历中序遍历是左中右先访问的是二叉树顶部的节点然后一层一层向下访问直到到达树左面的最底部再开始处理节点也就是在把节点的数值放进result数组中这就造成了处理顺序和访问顺序是不一致的。那么在使用迭代法写中序遍历就需要借用指针的遍历来帮助访问节点栈则用来处理节点上的元素。思路访问顺序从根开始一直向左走到底。处理顺序最左的子节点先处理然后根然后右子树。访问和处理顺序不一致→ 需要指针 栈。步骤指针cur指向根。循环条件cur ! null或栈非空。如果cur ! null入栈 往左。否则cur 为空弹出栈顶处理。指针指向右孩子。java public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); StackTreeNode stack new Stack(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { if (cur ! null) { stack.push(cur); cur cur.left; // 左 } else { cur stack.pop(); result.add(cur.val); // 中 cur cur.right; // 右 } } return result; }三、后序遍历左 → 右 → 根思路利用前序遍历的变体前序根 → 左 → 右栈先右后左。变体根 → 右 → 左栈先左后右。最后将结果反转→ 得到左 → 右 → 根。步骤根入栈。循环弹出栈顶 → 加入结果。先压左孩子再压右孩子保证出栈顺序是“根→右→左”。结果反转。java public ListInteger postorderTraversal(TreeNode root) { ListInteger result new ArrayList(); if (root null) return result; StackTreeNode stack new Stack(); stack.push(root); while (!stack.isEmpty()) { TreeNode node stack.pop(); result.add(node.val); if (node.left ! null) stack.push(node.left); if (node.right ! null) stack.push(node.right); } Collections.reverse(result); return result; }四、关键对比总结面试常问遍历方式访问与处理顺序是否一致是否需要指针核心技巧前序✅ 一致❌先右后左入栈中序❌ 不一致✅指针一路向左再处理后序❌ 不一致❌反向收集 反转结果结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励