如何高效计算Python字典中叶子的数量、平均宽度与高度？

先明确树形结构约定 #

假设你的树形字典遵循以下规则：

• 叶子节点包含width和height字段，无children字段
• 非叶子节点包含children字段（值为子节点列表），无width/height字段

示例初始化代码：

tree = {
    "name": "root",
    "children": [
        {"name": "leaf1", "width": 10, "height": 20},
        {
            "name": "branch",
            "children": [
                {"name": "leaf2", "width": 15, "height": 25},
                {"name": "leaf3", "width": 20, "height": 30}
            ]
        }
    ]
}

方法1：递归遍历（代码最简洁） #

利用递归天然适配树形结构的特性，通过生成器遍历所有叶子节点后完成统计：

def count_and_avg(tree):
    # 递归生成所有叶子节点的(width, height)
    def get_leaves(node):
        if "children" in node:
            for child in node["children"]:
                yield from get_leaves(child)
        else:
            yield (node["width"], node["height"])
    
    leaves = list(get_leaves(tree))
    count = len(leaves)
    if count == 0:
        return {"count": 0, "avg_width": 0, "avg_height": 0}
    total_width = sum(w for w, h in leaves)
    total_height = sum(h for w, h in leaves)
    return {
        "count": count,
        "avg_width": total_width / count,
        "avg_height": total_height / count
    }

# 调用示例
result = count_and_avg(tree)
print(result)  # 输出: {'count': 3, 'avg_width': 15.0, 'avg_height': 25.0}

方法2：迭代栈遍历（避免递归深度限制） #

如果树形结构层级极深，递归会触发RecursionError，用栈实现迭代遍历更稳妥，效率也更高：

def count_and_avg_iter(tree):
    stack = [tree]
    total_width = 0
    total_height = 0
    count = 0
    
    while stack:
        node = stack.pop()
        if "children" in node:
            # 子节点压栈，顺序不影响统计结果
            stack.extend(node["children"])
        else:
            count += 1
            total_width += node["width"]
            total_height += node["height"]
    
    return {
        "count": count,
        "avg_width": total_width / count if count > 0 else 0,
        "avg_height": total_height / count if count > 0 else 0
    }

# 调用示例
result = count_and_avg_iter(tree)
print(result)  # 输出同上

方法3：生成器+统计函数（复用性更强） #

把遍历逻辑单独封装成通用生成器，统计逻辑用Python内置函数简化，代码更模块化：

def iterate_leaves(tree):
    stack = [tree]
    while stack:
        node = stack.pop()
        if "children" in node:
            stack.extend(node["children"])
        else:
            yield node

# 统计部分一行搞定
leaves = list(iterate_leaves(tree))
count = len(leaves)
result = {
    "count": count,
    "avg_width": sum(leaf["width"] for leaf in leaves)/count if count else 0,
    "avg_height": sum(leaf["height"] for leaf in leaves)/count if count else 0
}

方案对比 #

• 递归法：代码最简洁，可读性高，但不适用于层级极深的树
• 迭代栈法：无深度限制，效率略高于递归，适合大规模树形结构
• 生成器法：遍历逻辑可复用，统计代码更灵活，适合需要多次处理叶子节点的场景

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