二叉树的深度遍历（为什么要遍历二叉树）

前言

大家好，我是bigsai，好久不见，甚是想念!

今天带大家征服二叉树的前中后序遍历，包含递归和非递归方式，学到就是赚到!

很多时候我们需要使用非递归的方式实现二叉树的遍历，非递归枚举相比递归方式的难度要高出一些，效率一般会高一些，并且前中后序枚举的难度呈一个递增的形式，非递归方式的枚举有人停在非递归后序，有人停在非递归中序，有人停在非递归前序(这就有点拉胯了啊兄弟)。

我们回顾递归，它底层其实是维护一个栈，将数据存到栈中，每次抛出栈顶的数据进行处理(也就是递归、dfs的方向化、极端化枚举特征非常明显)，我们驾驭递归的时候更重要的是掌握上下层之间的逻辑关系。

而非递归方式我们除了需要掌握上下层的逻辑关系之外，要手动的处理各种条件变更的细节， 递归是一个一来一回的过程，如果我们的逻辑只是在单趟的来或者回中还好，有时候甚至要自己维护来和回的状态，所以逻辑上难度还是比较大的。

二叉树的前序遍历

二叉树的前序遍历是最简单的，其枚举方式就是一个最简单的dfs，学会了二叉树的前序遍历，那么后面入门dfs就容易很多。

二叉树的前序遍历的枚举规则为：根结点 ---> 左子树 ---> 右子树，也就是给定一棵树，输出操作当前节点，然后枚举左子树(左子树依然按照根左右的顺序进行)，最后枚举右子树(右子树也按照根左右的顺序进行)，这样得到的一个枚举序列就是二叉树的前序遍历序列(也叫先序)。

前序遍历在二叉树树的顺序可以看下图(红色箭头指向的表示需要访问的，可以看出从父节点枚举下来第一次就要被访问)。

在具体实现的方式上，有递归方式和非递归方式实现。

递归

递归方式实现的二叉树前序遍历很简单，递归我们只需要考虑初始情况、结束边界、中间正常点逻辑。

初始情况：从root根节点开始枚举，函数执行传入root根节点作为参数。

结束边界：节点的左(或右)子节点为null那么就停止对应节点的递归执行。

正常点逻辑：先处理当前点(存储或输出)，递归调用枚举左子树(如果不为null),递归调用枚举右子树(如果不为null)。

刚好力扣144二叉树的前序遍历可以尝试ac：

1. classSolution{
2. List<Integer>value=newArrayList();
3. publicList<Integer>preorderTraversal(TreeNoderoot){
4. qianxu(root);
5. returnvalue;
6. }
7. privatevoidqianxu(TreeNodenode){
8. if(node==null)
9. return;
10. value.add(node.val);
11. qianxu(node.left);
12. qianxu(node.right);
13. }
14. }

非递归

非递归的前序还是非常简单的，前序遍历的规则是：根节点，左节点，右节点。但是根左方向一直下去，手动枚举又没有递归回的过程，一直下去我们怎么找到回来时候的右几点呢?

用栈将路过的节点先存储，第一次枚举节点输出储存然后放入栈中，第二次就是被抛出时候枚举其右侧节点。

它的规则大致为：

一直访问当前节点并用栈存储，节点指向左节点，直到左孩子为null。

抛出栈顶不访问。如果有右节点，访问其右节点重复步骤1，如有没右节点，继续重复步骤2抛出。

这样的一个逻辑，就会从根出发一直先往左访问，访问结束根、左之后再访问右节点(子树)，得到一个完成的前序遍历的序列。

具体实现的代码为：

1. classSolution{
2. publicList<Integer>preorderTraversal(TreeNoderoot){
3. List<Integer>value=newArrayList();
4. Stackq1=newStack();
5. while(!q1.isEmpty()||root!=null)
6. {
7. while(root!=null){
8. value.add(root.val);
9. q1.push(root);
10. root=root.left;
11. }
12. root=q1.pop();//抛出
13. root=root.right;//准备访问其右节点
15. }
16. returnvalue;
17. }
18. }

二叉树的中序遍历

二叉树的中序遍历出现的频率还是蛮高的，如果是二叉排序树相关问题还是蛮多的，你要知道二叉排序树的中序遍历是一个有序的序列，如果求二叉排序树的topk问题，非递归中序那效率是非常高的。

中序遍历在二叉树树的顺序可以看下图(红色箭头指向的表示需要访问的，可以看出如果子树为null，那肯定要访问，否则就是从左子树回来的时候才访问这个节点)。

递归方式

递归方式实现很简单，其逻辑和前序递归相似的，力扣94刚好有二叉树中序遍历,这里我直接放代码：

1. classSolution{
2. publicList<Integer>inorderTraversal(TreeNoderoot){
3. List<Integer>value=newArrayList<Integer>();
4. zhongxu(root,value);
5. returnvalue;
6. }
7. privatevoidzhongxu(TreeNoderoot,List<Integer>value){
8. if(root==null)
9. return;
10. zhongxu(root.left,value);
11. value.add(root.val);
12. zhongxu(root.right,value);
14. }
15. }

非递归方式

非递归的中序和前序是非常相似的，前序遍历的规则是：根节点，左节点，右节点。中序遍历的顺序是左节点，根节点，右节点 ，在前序中先根后左其实是有点覆盖的关系(这个左就是下一个跟)，在其非递归枚举实现上我们访问右节点时候是先抛出父节点不访问，直接访问父节点的右节点，如果抛出父节点访问这个父节点，其实它就是一个中间顺序的节点。

它的规则大致为：

枚举当前节点(不存储输出)并用栈存储，节点指向左节点，直到左孩子为null。

抛出栈顶访问。如果有右节点，访问其右节点重复步骤1，如有没右节点，继续重复步骤2抛出。

这样的一个逻辑，就会形成一个中序序列，因为叶子节点的左右都为null，这样的规则依然满足中序。

实现代码为：

1. classSolution{
2. publicList<Integer>inorderTraversal(TreeNoderoot){
3. List<Integer>value=newArrayList<Integer>();
4. Stackq1=newStack();
5. while(!q1.isEmpty()||root!=null)
6. {
7. while(root!=null){
8. q1.push(root);
9. root=root.left;
10. }
11. root=q1.pop();//抛出
12. value.add(root.val);
13. root=root.right;//准备访问其右节点
15. }
16. returnvalue;
17. }
18. }

二叉树的后序遍历

二叉树的后序遍历非递归方式实现起来难度最大的，能够手写非递归后序，一定能亮瞎面试官的眼!

后序遍历在二叉树树的顺序可以看下图(红色箭头指向的表示需要访问的，可以看出如果子树为null，那肯定要访问，否则就是从右子树回来的时候才访问这个节点)。

递归

二叉树递归方式后序遍历很简单，跟前序中序的逻辑一样，在力扣145有后序的code测试大家可以自己尝试一下。

这里直接放我写的后序递归方式：

1. classSolution{
2. List<Integer>value=newArrayList<>();
3. publicList<Integer>postorderTraversal(TreeNoderoot){
4. houxu(root);
5. returnvalue;
6. }
7. privatevoidhouxu(TreeNoderoot){
8. if(root==null)
9. return;
10. houxu(root.left);
11. houxu(root.right);//右子树回来
12. value.add(root.val);
13. }
14. }

非递归

非递归的后序就稍微难一点了，大家可以回顾一下二叉树的前序和中序遍历，其实都是只用一个栈直接抛出就可以找到右节点，抛出后栈就空了，但是这个后序遍历的顺序是 左子树 ---> 右子树 --->根节点，也就是处理完右节点，还要再回到根节点访问。所以从逻辑结构上和前序、中序的非递归实现方式有一些略有不同。

前序，中序遍历的顺序提取为：

前序: 中入栈—>左入栈—>左孩子入出—>左出栈—>中出栈—>右入栈—>右孩子入出—>右出栈

前序遍历同一大流程按照入栈顺序即形成一个前序序列

中序: 中入栈—>左入栈—>左孩子入出—>左出栈—>中出栈—>右入栈 —>右孩子入出—>右出栈

中序遍历同一大流程按照出栈顺序即形成一个中序序列

但是后序的话应该怎么考虑呢?

其实就是在从左孩子到中准备出栈的时候，先不出栈记成第一次，再将它放入栈中，如果从右孩子返回那么这个节点就是第三次遍历(第一次访问中，然后枚举左返回第二次，枚举右返回第三次)，这时候将其抛出就形成一个后序。

如果不理解这里画了一个简单的图帮助理解：

思路理解了，怎么实现呢?最简单的就是使用一个hashmap存储节点访问次数。

附一下个人实现的代码：

1. classSolution{
2. publicList<Integer>postorderTraversal(TreeNoderoot){
3. List<Integer>value=newArrayList();
4. Stackq1=newStack();
5. Map

如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）

您的姓名 *

身份证号码 *

手机号码 *

选择地区 *

详细地址 *

留言备注 *