Строка значений вместо их печати во время рекурсии

Question

Итак, я написал этот фрагмент кода для печати всех корневых путей листьев двоичного дерева, и когда он попадает в базовый регистр, он печатает каждый путь, вместо этого я хотел бы сохранить его в чтобы в итоге у меня был список списков, содержащих каждый путь. Я пробовал несколько вещей, таких как использование рекурсии хвоста или использование другого глобального списка, но я не могу его правильно реализовать.

def rootleafPath(self, root): 
    global arr 
    if root is None: 
     return 
    arr.append(root.rootid) 
    if self.isLeaf(root): 
     print arr 
    self.rootleafPath(root.left) 
    self.rootleafPath(root.right) 
    arr.pop() 

Это возвращает

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

в то время как я хочу, чтобы моя функция возвращает список, как [[1, 2, 4], [1, 2, 5], [1, 3]]

У меня возникла эта проблема в большинстве моих рекурсивных решений, где мне нужно сохранить результат, когда он попадает в базовый регистр вместо его печати.

Answer 1

Ваш алгоритм рекурсивного пути должен возвращать список списков на каждом шаге. Если вы находитесь на листовом узле, он должен вернуть список с одним списком, содержащим идентификатор этого узла. В противном случае он должен добавить идентификатор текущего узла в каждый из списков, возвращаемых левым или правым узлами, а затем вернуть этот новый список. Сортировать трудно объяснить, так что я написал код :)

class Node(object): 
    def __init__(self, root_id, left=None, right=None): 
     self.root_id = root_id 
     self.left = left 
     self.right = right 
    def is_leaf(self): 
     if self.left or self.right: 
      return False 
     return True 

def path(node): 
    if node.isLeaf(): 
     return [[node.root_id]] 
    left_paths = [[node.root_id] + p for p in path(node.left)] if node.left else [] 
    right_paths = [[node.root_id] + p for p in path(node.right)] if node.right else [] 
    return left_paths + right_paths 

tree = Node(0,Node(1, Node(2), Node(3, right=Node(4))), Node(5, Node(6))) 

path(tree) => [[0, 1, 2], [0, 1, 3, 4], [0, 5, 6]] 

Используя глобальный массив трудно, потому что на каждом уровне рекурсии, вы должны были бы знать состояние программы. Это гораздо проще разорвать эту проблему на два этапа:

1. Если я в листовом узле, то, что я должен вернуться, что представляет собой дерево, если этот лист узел был единственным узлом в дереве
2. Если я нахожусь на узле с детьми, что они должны возвращать мне, чтобы полностью представить свое поддерево.

В этом случае узел лист должен возвращать список одного списка, содержащего это идентификатор: вернуть [[node.root_id]]

И если узел находится где-то внутри дерева, оно должно ожидать списки списков из своих дочерних элементов, которые описывают поддерево. Затем он должен добавить свой идентификатор в качестве первого элемента каждого подсписок, а затем вернуть конкатенированный результат всех его дочерних списков.

Надеюсь, это поможет!