queue - 不使用队列可以进行广度优先搜索或广度优先遍历吗？

Question

我记得并检查过，遍历树或爬行网络广度优先 (BFS) 的常用方法是使用队列。实际上有没有办法不使用队列来实现它？

Answer 1

我知道这个问题现在很老了，但我只是想回答。您可以使用数组、链表(或任何其他线性容器)而不使用递归来执行此操作。保留两个容器，old和 new ，并交换 old与 new当您遍历 old 中的所有项目时.非常类似于队列的实现。

在 Python 中，它看起来像:

def breadth_first(root):
    if not root:
        return
    old = []
    new = []
    old.append(root)
    while old:
        for n in old:
            process(n)  # Do something
            if n.left:
                new.append(n.left)
            if n.right:
                new.append(n.right)
        old = new
        new = []

运行时复杂度将与队列实现相同，O(n)。