BFS(广度优先搜索)树遍历是一种按照层级顺序遍历树的方法。下面是一个示例代码,演示如何使用BFS树遍历来遍历一个树:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bfs_tree_traversal(root):
if root is None:
return []
result = []
queue = [root] # 使用队列来存储待访问的节点
while len(queue) > 0:
level_size = len(queue) # 当前层级的节点个数
level_result = []
for _ in range(level_size):
node = queue.pop(0) # 取出队列中的第一个节点
level_result.append(node.val)
if node.left:
queue.append(node.left) # 将左子节点加入队列
if node.right:
queue.append(node.right) # 将右子节点加入队列
result.append(level_result) # 将当前层级的结果加入总结果列表
return result
这段代码定义了一个TreeNode
类来表示树节点,其中包含一个val
属性,以及左右子节点的引用。bfs_tree_traversal
函数接受一个树的根节点作为参数,返回一个列表,其中按层级顺序存储了树的节点值。
在函数内部,我们首先检查根节点是否为空,如果是,则直接返回空列表作为结果。
然后,我们创建一个空列表result
来存储最终的结果,以及一个队列queue
来存储待访问的节点。我们将根节点加入队列中。
接下来,我们使用一个循环来遍历队列中的节点。在循环的每一次迭代中,我们首先获取当前层级的节点个数。然后,我们创建一个空列表level_result
来存储当前层级的节点值。
在接下来的循环中,我们依次取出队列中的节点,并将其值加入level_result
列表中。同时,我们检查当前节点是否有左子节点和右子节点,如果有,就将它们加入队列中。
完成内层循环后,我们将level_result
列表加入result
列表中,表示当前层级的节点值已经遍历完毕。
最后,我们返回result
列表作为最终结果。
希望这个示例能够帮助你理解BFS树遍历的解决方法。
上一篇:BFSShortestPathwithaTwist算法
下一篇:BFS树转换为图