假设我将所有直接连接的节点作为字典中的列表，如何打印二叉树的所有可能路径？

Question

我有一棵节点树：[1,2,3,4,5] 以 1 为根。可以表示为：

我有一个字典，其中的键作为节点，它们包含与其相连的节点列表，

my_dict = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}

我想从这本字典中打印出从根节点到叶节点的所有可能路径，如列表：

output: [[1,2,4],[1,2,5],[1,3]]

我试过的是，

l = list()
root = 1
def path_finder(root):
    l.append(root)
    prev = root
    for val in my_dict[root]:
        print(val)
        path_finder(val)
        if root == prev:
            print("End of path")

哪个returns：

2
4
End of path
5
End of path
End of path
3
End of path

我完全被困在这个问题上，任何帮助将不胜感激。提前致谢:-)

Answer 1

您可以使用递归生成器：

my_dict = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}
def get_paths(s, c = []):
  if not my_dict[s]:
     yield c+[s]
  else:
     for i in my_dict[s]:
       yield from get_paths(i, c+[s])

print(list(get_paths(1)))

输出：

[[1, 2, 4], [1, 2, 5], [1, 3]]

假设我将所有直接连接的节点作为字典中的列表，如何打印二叉树的所有可能路径？

How to print all possible paths of a binary tree given that I have all directly connected nodes as a list in a dictionary?

python

tree

recursion

binary-tree

python-3.x