Python实现：用广度优先搜索统计字典每层节点数量

需求说明 #

给定如下嵌套字典表示的树形结构：

d = {'title': 'Root', 'children': [
        {'title': 'Child 1','children': [
            {'title': 'Grandchild 11', 'children': [
                {'title': 'Great Grandchild 111', 'children': []}
            ]}
        ]},
        {'title': 'Child 2', 'children': [
            {'title': 'Grandchild 21', 'children': []}
        ]},
        {'title': 'Child 3', 'children': [
            {'title': 'Grandchild 31', 'children': []}
        ]}
    ]}

需要编写Python函数，接收该字典作为参数，返回整数列表，列表元素为广度优先搜索得到的各层级节点数量。示例预期输出为 [1, 3, 3, 1]。

实现代码 #

def count_level_nodes(tree):
    if not tree:
        return []
    result = []
    queue = [tree]
    while queue:
        # 统计当前层节点数
        level_size = len(queue)
        result.append(level_size)
        # 遍历当前层所有节点，收集下一层子节点
        for _ in range(level_size):
            node = queue.pop(0)
            queue.extend(node['children'])
    return result

代码说明 #

• 用队列实现广度优先遍历：初始时将根节点加入队列
• 每次循环先获取当前队列长度（即当前层的节点数），加入结果列表
• 遍历当前层的每个节点，将其所有子节点加入队列，为下一层遍历做准备
• 循环直到队列为空，此时所有层级的节点数都已统计完成

测试验证 #

将示例字典传入函数：

print(count_level_nodes(d))  # 输出: [1, 3, 3, 1]

符合预期结果。

内容的提问来源于stack exchange，提问作者doctorhandshake