二叉树的遍历问题可以说是基础内容,而且必须要掌握的,下面我将使用递归和辅助栈的方式来实现二叉树的前、中、后序遍历!具体的理论和实现思路,可以看一下左神的算法面试课程中的二叉树(1),再进行编码和实践,有啥疑惑可以评论区留言哈!
1 使用递归方式实现三种遍历方式
1.1 前序遍历
遍历方式: 根 -> 左 -> 右
1 | class Solution { |
时间复杂度:O(N) ,访问每个节点恰好一次
空间复杂度:O(N),取决于树的结构,最坏情况存储整棵树,因此空间复杂度是 O(N)
ps:本文章中的时间、空间复杂度都是O(N),为了文章的简洁性,下面将不再阐述
1.2 中序遍历
遍历方式: 左 -> 根 -> 右
1 | class Solution { |
1.3 后序遍历
遍历方式: 左 -> 右 -> 根
1 | class Solution { |
2 使用非递归方式实现三种遍历方式
2.1 前序遍历
遍历方式: 根 -> 左 -> 右
1 | class Solution { |
2.2 后序遍历(注意这里是后序遍历emmm)
遍历方式: 左 -> 右 -> 根
方法一:前序遍历的顺序为 根->左->右,与后序遍历的逆序(根->右->左)有些相似,因此可以使用前序遍历的思想,最后再倒置向量即可。
1 | class Solution { |
方法二:使用两个栈实现(其实和方法一基本是一样的,多开了一个栈)
1 | class Solution { |
方法三:使用一个栈实现
1 | class Solution { |
2.3 中序遍历
遍历方式: 左 -> 根 -> 右
1 | class Solution { |
结语:①如果你是小白,之前没有接触过二叉树相关问题的话,代码可能会有点难理解。可以跟着文章开头的视频链接,跟着思路,并食用代码实现,反复练习效果更佳!(可以先记住一个简单常用的套路解决问题)
②如果你是个大佬,对上述代码有什么改进或优化的地方,欢迎指出!
- 本文作者: a_Gen
- 本文链接: http://imaginee.cn/2020/01/31/LeetCode 94.144.145. 使用递归和非递归方式解决二叉树的三种遍历问题/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!