宽度优先搜索python

下面是一个基本的宽度优先搜索（BFS）Python 实现，其中包括一个示例用例：

from collections import deque

# 定义一个二叉树结构
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def bfs(root):
    # 如果根节点为空，则返回空列表
    if not root:
        return []

    # 创建队列，并将根节点放入其中
    queue = deque([root])
    result = []

    # 当队列不为空时，循环执行
    while queue:
        level_size = len(queue)
        current_level = []

        # 对当前队列中的节点进行处理
        for i in range(level_size):
            # 从队列中弹出一个节点
            node = queue.popleft()
            current_level.append(node.val)

            # 将该节点的左右子节点放入队列中
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        # 将当前层的结果添加到最终结果中
        result.append(current_level)

    return result

# 创建一个二叉树
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

# 运行 BFS 算法
print(bfs(root))  # [[3], [9, 20], [15, 7]]

这个算法基于队列数据结构实现，它的主要思想是按层遍历二叉树，从根节点开始，逐层将节点加入队列中，并在处理每一层的节点时，将其子节点放入队列中。在此过程中，我们可以记录每一层的节点值，并将其添加到结果列表中。最后，返回所有层的结果列表。

这个算法的时间复杂度是 O(N)，其中 N 是二叉树中的节点数。需要注意的是，由于我们需要存储每一层的节点值，因此空间复杂度是 O(N)。