本文主要是介绍二叉树的前序、中序、后序、层序遍历，递归和迭代两大类解题思路，每类细分不同解法【完整版】附PDF文档，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二叉树文章系列：
- 二叉树的前序遍历
- 二叉树的中序遍历
- 二叉树的后序遍历
- 二叉树的层序遍历
- 二叉树的前序、中序、后序、层序遍历【解法完整版】
本文目录
- 一、二叉树的前序遍历
- 1.1 解题思路：递归
- 1.2 解题思路：迭代（方法1）
- 1.3 解题思路：迭代（方法2）
- 二、二叉树的中序遍历
- 2.1 解题思路：递归
- 2.2 解题思路：迭代
- 三、二叉树的后序遍历
- 3.1 解题思路：递归
- 3.2 解题思路：迭代（方法1）
- 3.3 解题思路：迭代（方法2）
- 3.4 解题思路：迭代（方法3）
- 四、二叉树的层序遍历
- 4.1 解题思路：广度优先搜索BFS
- 4.2 解题思路：深度优先搜索DFS
一、二叉树的前序遍历
二叉树的前序遍历的记忆法则是“根左右"，即先遍历根节点，再遍历左子树节点，再遍历右子树节点。
以上图为例，前序遍历的结果是【A, B, D, E, C, F, G】
1.1 解题思路：递归
递归是我们实现前中后序遍历最常用的方法。
什么问题可以采用递归求解呢？
需要满足三个条件：
- 一个问题的解可以分解为若干个子问题的解；
- 这个问题与分解的子问题，除了数据规模不同外，求解思路相同
- 存在递归终止条件。
那么在知道一个问题可以采用递归实现之后，如何写出递归代码呢？
关键在于能写出递归公式，找到终止条件。
在二叉树的前序遍历问题上，它的递归公式是:
preorder(node) = print node —> preorder(node->left) --> preorder(node->right)
它的终止条件是：
node 是否为空，为空则返回。
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;preorder(res, root);return res;}void preorder(vector<int>& res, TreeNode* root){if(!root) return;res.emplace_back(root->val);preorder(res, root->left);preorder(res, root->right);}
};
1.2 解题思路：迭代（方法1）
在递归方法实现过程中，它的底层是基于系统栈的结构来实现的。因此，我们可以使用栈的数据结构来辅助实现基于迭代方式的前序遍历。
具体思路为：
- 初始化栈stack，初始化输出列表res
- 根节点入栈
- while(栈不为空)，在循环体内部：
- 栈顶元素出栈
- 栈顶元素添加到输出列表
- 如果栈顶元素的右子树节点不为空，将右子树节点入栈
- 如果栈顶元素的左子树节点不为空，将左子树节点入栈
- 返回输出列表res
这篇关于二叉树的前序、中序、后序、层序遍历，递归和迭代两大类解题思路，每类细分不同解法【完整版】附PDF文档的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
