树的宽度优先遍历，Python

Question

我先计算出树的深度。

def _dfs(tree, res):
    if tree:
        res += [tree.key]
        _dfs(tree.left, res)
        _dfs(tree.right, res)
    return res

我似乎找不到广度优先搜索的解决方案。需要使用队列还是堆栈？

谢谢！！

Answer 1

你可以和德克斯一起去。这是Magnus-Lie-Hetland（使用FIFO队列）的bfs的经典实现。

from collections import deque

def bfs(G, s):
    P, Q = {s: None}, deque([s]) 
    while Q:
        u = Q.popleft() 
        for v in G[u]:
            if v in P: continue 
            P[v] = u 
            Q.append(v)
    return P

Answer 2

是的，您必须使用队列来保存已检查但尚未递归到的节点。

从队列中的根节点开始，然后重复[pop a node and for each of its children，perform anything action you need（res += [tree.key]）并将其推送到队列中]。