如何用Python获取字典列表的所有层级路径？

输入的字典列表如下：

arr = [
    {'name': "item1", 'parent': None},
    {'name': "item2", 'parent': None},
    {'name': "item3", 'parent': None},
    {'name': "item4", 'parent': "item1"},
    {'name': "item5", 'parent': "item1"},
    {'name': "item6", 'parent': "item5"}
]

期望输出格式：

item1 -> item4
item1 -> item5 -> item6
item2
item3

实现思路与代码 #

核心思路是先把数据转换成父节点到子节点的映射字典，方便快速查找每个节点的子节点，再通过递归遍历每个根节点（parent为None的节点），生成所有完整路径。

代码实现：

def get_all_paths(items):
    # 构建父节点到子节点的映射字典
    parent_map = {}
    for item in items:
        parent = item["parent"]
        if parent not in parent_map:
            parent_map[parent] = []
        parent_map[parent].append(item["name"])
    
    # 递归生成路径的内部函数
    def build_path(current_node, current_path):
        new_path = current_path + [current_node]
        # 获取当前节点的子节点
        children = parent_map.get(current_node, [])
        if not children:
            # 没有子节点，返回格式化后的路径字符串
            return [" -> ".join(new_path)]
        # 有子节点，递归处理每个子节点
        paths = []
        for child in children:
            paths.extend(build_path(child, new_path))
        return paths
    
    # 收集所有根节点的路径
    all_paths = []
    for root in parent_map.get(None, []):
        all_paths.extend(build_path(root, []))
    
    return all_paths

# 测试执行
arr = [
    {'name': "item1", 'parent': None},
    {'name': "item2", 'parent': None},
    {'name': "item3", 'parent': None},
    {'name': "item4", 'parent': "item1"},
    {'name': "item5", 'parent': "item1"},
    {'name': "item6", 'parent': "item5"}
]

paths = get_all_paths(arr)
for path in paths:
    print(path)

代码说明：

1. 构建映射字典：遍历输入列表，将每个节点按父节点分组，生成parent_map，比如None对应['item1', 'item2', 'item3']，item1对应['item4', 'item5']。
2. 递归生成路径：从每个根节点出发，不断向下查找子节点，直到没有子节点时，将当前路径格式化为字符串返回。
3. 输出结果：调用函数后遍历结果打印，即可得到期望的层级路径格式。

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