广度优先遍历树，巨蟒

Question

我想通了深度优先遍历树。

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

我似乎无法找到广度优先搜索解决方案。将不得不使用队列或堆栈？

谢谢！

Answer 1

是的，你必须使用一个队列来保存您检查过，但还没有递归到节点。

从队列中的根节点开始，然后重复[弹出一个节点并为其每个子节点执行所需的任何操作（res += [tree.key]）并将其推送到队列中]。

Answer 2

你可以用双端去。这是一个经典的实现（使用FIFO队列）从马格努斯烈赫特兰的高炉。

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