Как напечатать все возможные пути двоичного дерева, если у меня есть все напрямую связанные узлы в виде списка в словаре?

Question

У меня есть дерево с узлами: [1,2,3,4,5] с 1 как root. Может быть представлен как:

И у меня есть словарь с ключами в качестве узлов, и они содержат список связанных с ними узлов,

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

Из этого словаря я хочу напечатать все возможные пути от root до конечных узлов в виде списка, например:

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")

Что возвращает:

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]]