递归树搜索生成所有路径数组：子-父字典的路径存储问题

我有一个以子节点为键、父节点为值的字典：

mydict = {'1': '0',
 '2': '0',
 '3': '1',
 '4': '3',
 '5': '3',
 '6': '2',
 '7': '6',
 '8': '7'  }

不知道树的子孙层级数，需要生成所有唯一的从根到叶子的路径，例如：
path1:[0,1,3,4], path2:[0,1,3,5], path3:[0,2,6,7,8]

我已经写了遍历整棵树并打印节点的函数：

def getvalues(x):
    xlist = [(i,j) for i,j in mydict.items() if j == x]
    for y in xlist:
        print(y[1], y[0])
        getvalues(y[0])


getvalues('0')

它的输出是：

0 1
1 3
3 4
3 5
0 2
2 6
6 7
7 8

但我不知道怎么存储各层级的中间值，转换成需要的数组格式。

可以通过递归时传递当前路径的方式存储中间节点，当遍历到叶子节点（无后续子节点的节点）时，将当前路径保存下来。具体实现如下：

mydict = {'1': '0',
 '2': '0',
 '3': '1',
 '4': '3',
 '5': '3',
 '6': '2',
 '7': '6',
 '8': '7'  }

def get_all_paths(start_node):
    paths = []
    def traverse(current_node, current_path):
        # 将当前节点加入路径，生成新路径（避免修改原路径）
        updated_path = current_path + [current_node]
        # 查找当前节点的所有子节点
        children = [child for child, parent in mydict.items() if parent == current_node]
        if not children:
            # 无子女则为叶子节点，保存完整路径
            paths.append(updated_path)
            return
        # 递归遍历每个子节点
        for child in children:
            traverse(child, updated_path)
    # 从根节点启动遍历，初始路径为空
    traverse(start_node, [])
    return paths

# 获取所有路径并格式化输出
all_paths = get_all_paths('0')
for idx, path in enumerate(all_paths, 1):
    # 可选：将字符串节点转为数字，匹配示例格式
    num_path = [int(node) for node in path]
    print(f'path{idx}:{num_path}')

代码说明 #

1. 外层函数get_all_paths负责初始化路径存储列表，并定义递归遍历的内部函数traverse。
2. traverse函数核心逻辑：
   • 每次递归先把当前节点追加到路径中，生成新的路径列表（避免递归间互相干扰）。
   • 查询当前节点的所有子节点，若没有子节点则直接保存路径；若有子节点，则对每个子节点递归调用traverse。
3. 运行后输出结果：

   path1:[0, 1, 3, 4]
   path2:[0, 1, 3, 5]
   path3:[0, 2, 6, 7, 8]
   

如果不需要将节点转为数字，直接移除num_path = [int(node) for node in path]这一行，输出原path即可。

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