如何从嵌套结构中获取所有子节点及后代节点列表？

给定父子关系字典：

{
    2: [8, 7],
    8: [9, 10],
    10: [11],
    15: [16, 17],
}

需要获取指定父节点的所有子节点、孙节点、曾孙节点等后代节点列表。例如父节点ID为2时，期望得到结果 [8, 7, 9, 10, 11]，嵌套层级无限制且不存在循环引用。

原代码及问题 #

编写的函数无法正确返回结果：

links = {
    2: [8, 7],
    8: [9, 10],
    10: [11],
    15: [16, 17],
}

def get_nested_children(parent_uid, acc = []):
    if parent_uid in links:
        acc = acc + links[parent_uid]
        print("[in loop]", acc)

        for child_uid in links[parent_uid]:
            get_nested_children(child_uid, acc)
    else:
        return acc

print(get_nested_children(2))

函数输出：

[in loop] [8, 7]
[in loop] [8, 7, 9, 10]
[in loop] [8, 7, 9, 10, 11]
None

问题分析 #

1. 返回逻辑缺失：只有当parent_uid不在字典中时才返回acc，递归调用时未接收并更新返回值，导致顶层函数没有返回结果，最终输出None。
2. 默认参数陷阱：默认参数acc = []会在函数定义时创建一次，多次调用会复用同一个列表，可能引发意外数据污染。

修正方案 #

递归版 #

links = {
    2: [8, 7],
    8: [9, 10],
    10: [11],
    15: [16, 17],
}

def get_nested_children(parent_uid):
    acc = []
    if parent_uid in links:
        # 添加当前节点的直接子节点
        acc.extend(links[parent_uid])
        # 递归获取每个子节点的后代并合并
        for child_uid in links[parent_uid]:
            acc.extend(get_nested_children(child_uid))
    return acc

print(get_nested_children(2))  # 输出: [8, 7, 9, 10, 11]

迭代版（广度优先遍历） #

适合层级较深的场景，避免递归栈溢出：

links = {
    2: [8, 7],
    8: [9, 10],
    10: [11],
    15: [16, 17],
}

def get_nested_children(parent_uid):
    descendants = []
    queue = [parent_uid]
    while queue:
        current = queue.pop(0)
        if current in links:
            children = links[current]
            descendants.extend(children)
            queue.extend(children)
    return descendants

print(get_nested_children(2))  # 输出: [8, 7, 9, 10, 11]

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