Блог

Представьте, что вы должны написать функцию, которая принимает в качестве аргументов дерево и значение x. Функция должна возвращать все пути от корня дерева к этому значению в виде списка. Если существует несколько путей, то функция возвращает список списков.

Вот что я получил до сих пор

 def path_finder(t,value):  paths = []  if label(t) == value:  return [label(t)]  for b in branches(t):  path = path_finder(b, value)  if path:  paths.append([label(t)] path)  return paths  

Однако, учитывая дерево t и значение x = 5, вот мой вывод

 t = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])  path_finder(t,5)  [[1,[2,5]],[1,5]]  

Похоже, это проблема с укладкой.

Есть какая-нибудь помощь в отладке?

Примечание: метка(t) —gt; значение корня

Я не знаю, существует ли стандартный класс дерева, который вы используете, поэтому я его создал.

 class tree():  def __init__(self, val, sub=[]):  self.val = val  self.sub = sub # a list of trees  def label(t):  return t.val def branches(t):  return t.sub  def path_finder(t, value):  paths = []  if label(t) == value:  paths.append([value])  for b in branches(t):  paths  = [[label(t)]   path for path in path_finder(b, value)]  return paths  t = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)]) for x in range(7):  print(x, path_finder(t, x))  

Основная коррекция находится на линии paths = [[label(t)] path for path in path_finder(b, value)] . Также обратите внимание , что когда label(t) == value я не сразу возвращаю список. Остановка кода в этот момент не приведет к нахождению каждого пути, например, когда узел 5 находится под другим узлом 5.

Выход:

 # 0 [] # when path_finder cannot find the value # 1 [[1]] # 2 [[1, 2]] # 3 [[1, 2, 3]] # 4 [[1, 2, 4]] # 5 [[1, 2, 5], [1, 5]] # 6 [[1, 2, 4, 6]]