二叉树的前序、中序、后序、层序遍历，递归和迭代两大类解题思路，每类细分不同解法【完整版】附PDF文档

本文主要是介绍二叉树的前序、中序、后序、层序遍历，递归和迭代两大类解题思路，每类细分不同解法【完整版】附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);}
};