求非二叉树各层级宽度的Python算法实现方案

解决思路 #

要计算非二叉树的各层级宽度，核心是**按层次遍历（BFS）**统计每一层的节点数量。步骤分为两步：

1. 从边列表构建树的邻接表结构，并确定根节点（无父节点的节点）
2. 通过BFS逐层遍历节点，记录每一层的节点总数

代码实现 #

def calculate_level_widths(edges):
    # 1. 构建邻接表：key是父节点，value是子节点列表
    adjacency = {}
    # 收集所有出现过的节点，用于找根节点
    all_nodes = set()
    target_nodes = set()
    
    for source, target in edges:
        if source not in adjacency:
            adjacency[source] = []
        adjacency[source].append(target)
        all_nodes.add(source)
        all_nodes.add(target)
        target_nodes.add(target)
    
    # 找到根节点：不在target_nodes里的节点
    root = next(node for node in all_nodes if node not in target_nodes)
    
    # 2. BFS层次遍历统计宽度
    level_widths = []
    from collections import deque
    queue = deque([root])
    
    while queue:
        # 当前层的节点数量就是宽度
        current_level_size = len(queue)
        level_widths.append(current_level_size)
        
        # 把当前层所有节点的子节点加入队列
        for _ in range(current_level_size):
            node = queue.popleft()
            # 注意叶子节点没有子节点，需要判断
            if node in adjacency:
                queue.extend(adjacency[node])
    
    return level_widths

# 测试输入
edges = [
    [11,1],[11,2],
    [10,11],[10,22],[10,33],
    [33,3],[33,4],[33,5],[33,6]
]

print(calculate_level_widths(edges))  # 输出: [1, 3, 6]

代码解释 #

• 邻接表构建：遍历边列表，用字典存储每个父节点对应的所有子节点，同时记录所有节点和被指向的节点（target_nodes），从而找出根节点（只有根节点不会出现在target_nodes中）。
• BFS遍历：用队列保存当前层的节点，每次循环先获取当前层的节点数（即宽度），然后将当前层所有节点的子节点加入队列，进入下一层循环，直到队列为空。

核心概念参考 #

• 广度优先搜索（BFS）：一种逐层遍历的搜索算法，天然适合处理分层统计类问题，能保证按层级顺序访问节点。
• 邻接表：非二叉树常用的存储结构，相比二叉树的左右指针，它可以灵活存储任意数量的子节点。

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