algorithm - 递归地执行广度优先搜索

Question

假设您想要递归地实现二叉树的广度优先搜索。你会怎么做？

是否可以仅使用调用堆栈作为辅助存储？

Answer 1

(我假设这只是某种思维练习，甚至是一个技巧性的家庭作业/面试问题，但我想我可以想象一些奇怪的场景，由于某种原因你不允许任何堆空间[一些真的很糟糕的自定义内存管理器？一些奇怪的运行时/操作系统问题？]而你仍然可以访问堆栈......)

广度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质非常相反，因此尝试使用调用堆栈(这是一个堆栈，因此得名)作为辅助存储(队列)几乎注定要失败，除非你正在做调用堆栈有些愚蠢可笑，你不应该这样。

出于同样的原因，您尝试实现的任何非尾递归本质上都是在算法中添加堆栈。这使得它不再对二叉树进行广度优先搜索，因此传统 BFS 的运行时等不再完全适用。当然，您总是可以轻松地将任何循环转换为递归调用，但这不是任何有意义的递归。

但是，正如其他人所展示的那样，有一些方法可以以一定的代价实现遵循 BFS 语义的东西。如果比较的代价是昂贵的但节点遍历是便宜的，那么作为@Simon Buchan确实如此，您可以简单地运行迭代深度优先搜索，只处理叶子。这意味着堆中没有存储增长的队列，只有一个局部深度变量，并且随着树一次又一次地遍历，堆栈在调用堆栈上一次又一次地建立起来。而作为 @Patrick注意，无论如何，由数组支持的二叉树通常以广度优先遍历顺序存储，因此对其进行广度优先搜索是微不足道的，也不需要辅助队列。