一起走进遍历二叉树的奇妙之旅：递归、迭代与统一迭代法全详解

一起走进遍历二叉树的奇妙之旅：递归、迭代与统一迭代法全详解

引用

CSDN

1.

https://blog.csdn.net/2301_79896470/article/details/146053622

生活的底片从来不是遥远的白日梦，而是热爱生活的自己

二叉树的遍历是指按照某种顺序访问树中的所有节点。常见的遍历方式分为两大类：深度优先遍历（DFS） 和 广度优先遍历（BFS）。以下是详细的遍历方式及其实现方法：

深度优先遍历（DFS）

深度优先遍历是从根节点出发，沿着一条路径尽可能深地访问节点，直到到达叶子节点，然后回溯到上一个节点继续遍历。DFS 有三种常见方式：

前序遍历（Preorder Traversal）

• 顺序：根节点 → 左子树 → 右子树
• 应用场景：复制树、表达式树的前缀表示。

中序遍历（Inorder Traversal）

• 顺序：左子树 → 根节点 → 右子树
• 应用场景：二叉搜索树的中序遍历结果是有序的。

后序遍历（Postorder Traversal）

• 顺序：左子树 → 右子树 → 根节点
• 应用场景：删除树、表达式树的后缀表示。

广度优先遍历（BFS）

广度优先遍历是按层次从上到下、从左到右访问节点。通常使用队列实现。

层序遍历（Level Order Traversal）

• 顺序：从上到下、从左到右逐层访问节点。
• 应用场景：求树的深度、按层打印节点。

遍历方式对比

二叉树的递归遍历

在递归遍历中，各个遍历的规律是：

• 前序遍历：中左右
• 中序遍历：左中右
• 后序遍历：左右中

二叉树的迭代遍历

迭代法就是借用栈的思想来实现二叉树的遍历，但是不同的遍历有不一样。

前序遍历

因为我们要满足出栈是是中左右的顺序，根据栈先进后出的特性，我们入栈的顺序应该是右左。

中序遍历

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点。

后序遍历

后序遍历是左右中，我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。

二叉树的统一迭代法

针对三种遍历方式，使用迭代法是可以写出统一风格的代码！我们的做法是，我们讲访问的节点直接加入栈中，但是如果是要处理的节点我们就在后面放入一个空指针。然后统一收割节点。

前序遍历

压栈顺序：右左中

中序遍历

压栈顺序：右中左

后序遍历

压栈顺序：中右左