打印给定文件夹和子文件夹中的所有文件,而不使用递归/堆栈

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
 }