前言
为什么要掌握非递归呢? 递归实现前中后序遍历十分轻松,二非递归就复杂许多了.
主要是递归有以下几个缺陷：
- 内存消耗：递归算法由于会在堆栈中不停地压入和弹出函数调用记录，因此会占用大量的内存，如果递归的次数过多，可能会导致栈溢出。
- 效率低下：递归算法的效率低下，因为每次递归都需要重新压入调用记录和恢复上一次的状态，这些操作都会增加额外的开销，导致递归算法效率低下，特别是在处理大量数据时会更为明显。
- 可读性较差：递归算法的代码一般会比较复杂，理解和维护难度较大，而且递归算法往往涉及到栈的使用，在理解和分析时需要一定的数学基础。
总结:主要害怕栈溢出,其次,可以增加一点点效率.
一、非递归实现"前序遍历"
题目链接:传送门
题目要求:
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
补充知识: 二叉树的前序遍历，又称为先序遍历，是指先访问节点本身，然后按照先左后右的顺序遍历其左右子树。具体步骤如下：
- 访问根节点。
- 遍历左子树，即对左子节点进行前序遍历。
- 遍历右子树，即对右子节点进行前序遍历。
方法一、思路分析:
- 根节点入栈.
- 栈顶元素入存入
vector,根节点出栈. - 右孩子入栈
- 左孩子入栈
因为我们要求:
先访问左孩子,再访问右孩子.
而栈是后进先出的结构,所以:
右孩子先入栈,左孩子后入栈.
步骤示例图:
(图片为博主:"初阶牛"原创,未经允许,不得复制)
结果:
