背景:之前在算法书上看到说所有的递归算法都可以写成非递归的形式。
那么遍历一个完全树的所有叶子节点,我看过两个算法,一个是递归调用,非常简单。
还有一个使用了队列:(c++ 和伪代码的混合表示)
queue.push(root);//根节点进队
while (!queue.isEmpty())
{
queue.push(root->left);
queue.push(root->right);
if (!queue.top()->hasChild())
{
print queue.top()->data;
}
queue.pop();
}
上面的算是非递归形式。
不过我想问的是,是不是说一定需要队列或者堆栈这样的辅助数据结构才能解决该问题?
因为我觉得之前的一些递归算法改成的非递归算法都没有用到什么数据结构。
比如合并排序的非递归形式。用到的仅仅是两个向量而已。
我一直认为递归算法改成非递归形式是有一定的模板可循的。如果辅助数据结构不可避免,是不是意味着所有的递归算法只是理论上可以写成递归形式,至于写不写的出来,还要看个人的数据结构水平?