二叉树遍历（前序、中序、后序）递归与迭代

二叉树遍历是数据结构中的经典问题，前序、中序、后序三种遍历方式通过递归或迭代实现，展现了算法设计的巧妙之处。无论是理解递归的简洁性，还是掌握迭代的栈模拟技巧，都能帮助开发者深入理解树结构操作。本文将带你探索不同遍历方式的实现逻辑与适用场景，感受算法之美。
递归与迭代的本质差异
递归实现二叉树遍历代码简洁直观。以前序为例，只需按“根-左-右”顺序递归调用即可。中序和后序只需调整访问顺序，但递归可能引发栈溢出问题。迭代法则通过显式栈模拟递归过程，例如前序遍历时先将根节点入栈，循环中弹栈访问并优先压入右子节点，再压左子节点，利用栈的LIFO特性实现反向处理。
中序遍历的迭代技巧
中序迭代需特殊处理访问顺序。核心思想是“左链入栈”：从根节点出发，将所有左子节点入栈，弹栈时访问节点并转向其右子树。这种“迂回”策略确保了左子树优先访问，完美复现递归的中序逻辑。后序迭代则更复杂，常需记录前驱节点或采用“根-右-左”逆序输出。
后序遍历的双栈妙用
后序迭代可通过双栈优化：主栈按“根-右-左”顺序压入节点，辅助栈反向存储结果。最终辅助栈的出栈顺序即为“左-右-根”的后序遍历。这种方法避免了复杂的节点状态标记，体现了空间换时间的思想。
应用场景与性能对比
递归适合小规模数据或代码可读性优先的场景，而迭代在大规模数据时更安全高效。例如，前序迭代适合快速克隆树结构，中序迭代常用于二叉搜索树的有序输出，后序迭代则在计算子树属性时优势明显。理解两者的适用性，能灵活应对不同需求。
通过对比递归与迭代的实现，我们不仅掌握了遍历的核心逻辑，更体会到算法设计中的平衡艺术。无论是递归的优雅还是迭代的稳健，都在解决实际问题中熠熠生辉。