假设您想实现二叉树的广度优先搜索递归地。你会怎样做呢？
是否可以仅使用调用堆栈作为辅助存储？
（我假设这只是某种思维练习，甚至是一个技巧作业/面试问题，但我想我可以想象一些奇怪的场景，由于某种原因你不允许任何堆空间[一些非常糟糕的习惯]内存管理器？一些奇怪的运行时/操作系统问题？]而你仍然可以访问堆栈......）
广度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎相反，因此尝试使用调用堆栈（这是一个堆栈，因此得名）作为辅助存储（队列）几乎注定会失败，除非您正在这样做调用堆栈中的一些愚蠢可笑的事情是你不应该做的。
同样，您尝试实现的任何非尾递归的本质本质上都是向算法添加堆栈。这使得它不再在二叉树上进行广度优先搜索，因此传统 BFS 的运行时等不再完全适用。当然，您总是可以轻松地将任何循环转换为递归调用，但这不是任何有意义的递归。
然而，正如其他人所演示的，有一些方法可以以一定的成本实现遵循 BFS 语义的东西。如果比较的成本很昂贵但节点遍历很便宜，那么@西蒙·巴肯这样做，您可以简单地运行迭代深度优先搜索，仅处理叶子。这意味着堆中没有存储增长的队列，只是一个本地深度变量，并且随着树被一遍又一遍地遍历，堆栈在调用堆栈上一遍又一遍地构建。并作为@Patrick值得注意的是，无论如何，由数组支持的二叉树通常都以广度优先遍历顺序存储，因此对其进行广度优先搜索将是微不足道的，也不需要辅助队列。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
