写在前面
最近看很多的面试题都有常见算法的迭代(非递归)写法这一类, 下面总结下这类问题的一些一般方法(我自己的心得体会, 如有不对欢迎大家批评指正).
在常见算法中, 涉及到二叉树等树型数据结构这样的基本上都有对应的递归写法, 但是由于递归调用的过程中会出现程序栈空间的开辟, 造成内存空间的浪费(尾递归不会), 并且每一次调用的栈帧都会保存很多并不会在之后调用中用到的参数,变量等, 这就进一步加大了内存的浪费, 所以递归算法虽然直观, 也应该去想一下对应的迭代方法, 这也算是程序优化的一种主要思路.
除了数据结构, 一些排序算法也用到了递归, 例如快速排序, 归并排序和堆排序, 这些排序算法用递归写直观不少, 但是掌握其迭代写法也很有必要.
下面给出我对于转换递归为迭代的一些主要思路:
-
用栈保存递归变量(递归中改变的值);
-
变量的入栈出栈顺序相反;
-
递归跳出条件和迭代终止条件一样;
- 基本框架:
while (!st.empty()){ /* 操作 */ } - 尾递归直接修改尾部传值即可.
算法:二叉树的遍历
这里写成迭代法当然需要自己开辟栈空间, (当然Morris遍历这种特殊的强大方法另说)