Найти все корень в путях листьев в двоичном дереве (в Python)

Question

У меня есть код в Python, который должен возвращать все корни в пути листа в двоичном дереве в виде списка (пример ["1- > 2-> 5 "," 1-> 3 "]). Исходный вопрос - из leetcode.

Мне нужна помощь в выяснении того, что не так с моим кодом и/или альтернативными решениями (желательно в Python). В приведенном выше примере мой код возвращает null, пока он должен фактически распечатать список, который я дал. Я также хотел бы получить представление о том, как вы подходите к этой проблеме, когда впервые видите этот вопрос.

Вот мой код:

def binaryTreePaths(self, root): 
     list1 = [] 
     if (root == None): 
      return [] 
     if (root.left == None and root.right == None): 
      return list1.append(str(root.val) + "->") 
     if (root.left != None): 
      list1.append(self.binaryTreePaths(root.left)) 
     if (root.right != None): 
      list1.append(self.binaryTreePaths(root.right)) 

Answer 1

• отсутствует оператор возврата
• нижнего уровня список рекурсия возвращается, а не одно значения (т.е. += против .append())
• значения в списке, возвращаемом более низкий уровень рекурсивного вызова должен быть добавлен с помощью «root->»

Итого:

def binaryTreePaths(self, root): 
    if root is None: 
     return [] 
    if (root.left == None and root.right == None): 
     return [str(root.val)] 
    # if left/right is None we'll get empty list anyway 
    return [str(root.val) + '->'+ l for l in 
      self.binaryTreePaths(root.right) + self.binaryTreePaths(root.left)] 

UPD: решение выше использует list comprehensions, одна из причин, почему мы любим Python так много. Вот расширенная версия: [? Почему же добавляет обратный ни в этом коде]

def binaryTreePaths(self, root): 
    if root is None: 
     return [] 
    if (root.left == None and root.right == None): 
     return [str(root.val)] 

    # subtree is always a list, though it might be empty 
    left_subtree = self.binaryTreePaths(root.left) 
    right_subtree = self.binaryTreePaths(root.right) 
    full_subtree = left_subtree + right_subtree # the last part of comprehension 

    list1 = [] 
    for leaf in full_subtree: # middle part of the comprehension 
     list1.append(str(root.val) + '->'+ leaf) # the left part 

    return list1