1回答

liuyubobobo

2018-06-08

已采纳

首先，一般的递归算法转非递归算法，都可以通过使用自己的栈来模拟计算机的系统栈来进行。我在课程的《玩转算法面试》（https://coding.imooc.com/class/82.html）中，在讲和栈相关的问题的时候，专门使用了两个小节（6-2，6-3）来介绍相关的内容，有兴趣可以参考。如果没有买那个课程，也可以直接找来那一小节的代码自己进行研究。传送门：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/06-Stack-and-Queue/Course%20Code%20(C%2B%2B)/03-Non-Recursive-Implementation-of-a-Recursive-Algorithm

对于二叉树，其实有经典的非递归遍历算法，在这个课程的补充代码中有给出。这里说“经典”，是因为这个算法过程一般大学课堂上都会介绍的。不过个人认为，对于二叉树的遍历，所谓的经典非递归代码，其实对于深刻理解递归帮助不大，更是一种在二叉树领域的特殊算法。所以在这个课程中并没有进行特殊强调。不过从学习的角度，还是有必要掌握的：）

参考代码：https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C++)/Optional-09-Binary-Tree-Classic-Nonrecursive-Traversal

最后，对于二叉树的非递归遍历，有一个更神奇的方法，使用O(n)的时间复杂度和O(1)的空间复杂度（即不适用栈！），称为Morris遍历法。Morris遍历近乎不可能出现在面试（或者考研）中。不过有兴趣，也可以自己研究看。课程的补充代码中也给出了实现，可以参考这里：https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/05-Binary-Search-Tree/Course%20Code%20(C++)/Optional-10-Binary-Tree-Morris-Traversal

一般的递归转非递归，使用自己建立的栈来模拟系统栈的调用肯定可以完成。不过通常在一些特殊的问题上，也可以使用更巧妙的方式写出非递归代码。比如上面例子中二叉树遍历的教科书式经典非递归算法，在我看来就不是通常的思路。这方面就需要自己逐渐积累了。另外一个好的例子就是动态规划。动态规划的所有问题都可以采用记忆化搜索的递归方法解决，但与此同时，也可以使用迭代式的动态规划解决。这里将递归转成非递归，也不是靠模拟系统栈来完成的。对动态规划感兴趣，也可以参考我的《玩转算法面试》课程（https://coding.imooc.com/class/82.html），有专门的一章具体介绍动态规划算法入门：）

加油！

5

1

慕沐9313579

非常感谢！

2018-06-10

共1条回复