创建的二叉树后续非递归遍历结果为_一入递归深似海，从此offer是路人

前言

今天我们来总结二叉树的前中后序以及层次遍历的递归与非递归的写法。我们都知道二叉树遍历的递归写法很简单，但是面试的时候面试官往往考察的不是我们递归的写法，他们满怀期待你写出非递归的解法，而当你只会写递归方法时，offer已经与你渐行渐远了。

下面先一起来看一下二叉树各种遍历的顺序：

前序遍历：根结点 —> 左子树 —> 右子树（先遍历根节点，然后左右）
这棵树的前序遍历为：ABDEGHCF

中序遍历：左子树—> 根结点 —> 右子树（在中间遍历根节点）
这棵树的中序遍历为：DBGEHACF

后序遍历：左子树 —> 右子树 —> 根结点（最后遍历根节点）
这棵树的后序遍历为：DGHEBFCA

层次遍历：按层次遍历
这棵树的层次遍历为：ABCDEFGH

ps: 所谓的前序、中序、后续，就是对根节点而言的，左右的遍历顺序不变，前序就是根节点最先遍历，然后左右；中序就是把根节点放在中间遍历；后序则是把根节点放在最后遍历。

https://blog.csdn.net/qq_42651904/article/details/90288715

文章目录

• 前言
• 一、前序遍历
  • 1.递归解法
  • 2.非递归方法（栈）
• 二、中序遍历
  • 1.递归解法
  • 2.非递归方法（栈）
• 三、后序遍历
  • 1.递归解法
  • 2.非递归方法（栈）
• 四、层次遍历
  • 1.非递归解法（队列）
• 总结

一、前序遍历

1.递归解法

代码如下：

class

2.非递归方法（栈）

前序遍历是中左右，每次先处理的是中间节点，先将跟节点放入栈中，然后将右孩子加入栈，再加入左孩子。（因为栈的特性是先入后出，所以要先加入右孩子，再加入左孩子）

代码如下：

class

二、中序遍历

1.递归解法

代码如下：

class

2.非递归方法（栈）

中序遍历是左中右，每次先从根节点开始，一直遍历左子节点，并在遍历过程中将其入栈，然后取出栈顶元素，再指向右孩子。

代码如下：

class

三、后序遍历

1.递归解法

代码如下：

class

2.非递归方法（栈）

后序遍历是左右中，而先序遍历是中左右，那么我们只需要调整一下先序遍历的代码顺序（栈内先入左孩子，再入右孩子：这样出栈为“右左中”），最后反转res数组（得到“左中右”）。

代码如下：

class

四、层次遍历

1.非递归解法（队列）

层次遍历算法思想：
用一个队列保存被访问的当前节点的左右孩子以实现层次遍历。
在进行层次遍历的时候，设置一个队列结构，遍历从二叉树的根节点开始，首先将根节点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：

访问该元素所指向的节点

若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束

代码如下：

class

总结

以上就是二叉树前中后以及层次遍历的递归与非递归写法了，喜欢的就点个赞同和关注吧！！！

总结

以上是生活随笔为你收集整理的创建的二叉树后续非递归遍历结果为_一入递归深似海，从此offer是路人的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。