algorithm - 在不使用递归/堆栈的情况下打印给定文件夹和子文件夹中的所有文件

Question

我最近接受了一家知名公司的软件开发人员职位面试，这是被问到的问题之一:

“给定以下方法:

List subDirectories(String directoryName){ ... }; 
List filesInDirectory(String directoryName) { ... };

顾名思义，第一种方法返回输入目录 ('directoryName') 中直接子目录的名称列表，第二种方法返回此文件夹中所有文件的名称列表。

打印文件系统中的所有文件。"

我想了想，给了面试一个很明显的递归解法。然后她告诉我不要递归。由于递归使用调用堆栈，我告诉她我将使用辅助堆栈来代替，此时她告诉我也不要使用堆栈。不幸的是，我无法想出解决方案。我确实问过如何在没有递归/堆栈的情况下完成它，但她没有说。

如何做到这一点？

Answer 1

您想使用队列和 BFS 算法。

我想一些伪代码会很好:

files = filesInDirectory("/")
foreach (file in files) {
   fileQ.append(file)
}

dirQ = subDirectories("/")
while (dirQ != empty) {
   dir = dirQ.pop
   files = filesInDirectory(dir)
   foreach (file in files) {
      fileQ.append(file)
   }
   dirQ.append(subDirectories(dir))
}

 while (fileQ != empty) {
   print fileQ.pop
 }