Найти все корневые пути листьев в двоичном дереве (в Python)
У меня есть код в 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)) One Solution collect form web for “Найти все корневые пути листьев в двоичном дереве (в Python)”
- отсутствует оператор возврата
- список возвратов рекурсии нижнего уровня, а не одно значение (т.е.
+=vs..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 : вышеприведенное решение использует списки , одна из причин, по которой мы так любим 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