一尘不染

递归执行广度优先搜索

algorithm

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

是否可以仅将调用堆栈用作辅助存储?


阅读 328

收藏
2020-07-28

共1个答案

一尘不染

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

广度优先遍历通常使用队列,而不是堆栈。队列和堆栈的性质几乎是相反的,因此,除非您这样做,否则尝试将调用堆栈(即堆栈,因此称为名称)用作辅助存储(队列)注定会失败。对于您不应该使用的调用堆栈而言,这太愚蠢了。

同样,您尝试实现的任何非尾递归本质上实际上是在算法中添加了堆栈。这使得它不再在二叉树上进行广度优先搜索,因此传统BFS的运行时和其他条件不再完全适用。当然,您始终可以将任何循环简单地转换为递归调用,但这不是任何有意义的递归。

但是,正如其他人所证明的那样,有一些方法可以以某种代价实现一些遵循BFS语义的方法。如果比较的成本很高,而节点遍历的成本很低,则就像@SimonBuchan一样,您可以简单地运行深度优先的迭代搜索,仅处理叶子。这意味着堆中没有存储增长的队列,只有局部深度变量,并且在遍历树的过程中一遍又一遍地在调用堆栈上建立了堆栈。正如@Patrick所指出的,无论如何,数组支持的二叉树通常都以广度优先遍历的顺序存储,因此,在不需要辅助队列的情况下,对广度优先的搜索将是微不足道的。

2020-07-28