La función anterior AllPaths() agrega una matriz que contiene la ruta a cada hoja del árbol binario a la matriz global res .
El código funciona bien, pero quiero eliminar la variable global res y hacer que la función devuelva una matriz en su lugar. ¿Cómo puedo hacer eso?
class Node: def __init__(self, value, left=None, right=None) -> None: self.value = value self.left = left self.right = right res = [] def allPaths(node, arr=[]): if node: tmp = [*arr, node.value] if not node.left and not node.right: # Leaf res.append(tmp) allPaths(node.left, tmp) allPaths(node.right, tmp) root = Node(1) root.left = Node(2); root.left.left = Node(4); root.left.right = Node(5); root.right = Node(3); root.right.right = Node(6); """ 1 <-- root / \ 2 3 / \ \ 4 5 6 <-- leaves """ allPaths(root) print(res) # Output : [[1, 2, 4], [1, 2, 5], [1, 3, 6]]Una forma simple que le permite evitar las listas internas y la lista global por completo es hacer un generador que produzca los valores tal como vienen. Luego, puede pasar esto a la list para obtener el resultado final:
class Node: def __init__(self, value, left=None, right=None) -> None: self.value = value self.left = left self.right = right def allPaths(node): if node: if not node.left and not node.right: # Leaf yield [node.value] else: yield from ([node.value] + arr for arr in allPaths(node.left)) yield from ([node.value] + arr for arr in allPaths(node.right)) root = Node(1) root.left = Node(2); root.left.left = Node(4); root.left.right = Node(5); root.right = Node(3); root.right.right = Node(6); g = allPaths(root) list(g) # [[1, 2, 4], [1, 2, 5], [1, 3, 6]]Un método es hacerlo retrocediendo:
def allPaths(node, partial_res, res): if not node: return if not node.left and not node.right: res.append(partial_res[:] + [node.value]) return partial_res.append(node.value) allPaths(node.left, partial_res, res) allPaths(node.right, partial_res, res) partial_res.pop() res = [] allPaths(root, [], res) print(res)Podría pasar la ruta actual en la recursividad:
def allPaths(node,path=[]): if not node: return # no node, do nothing fullPath = path + [node.value] if node.left or node.right: # node is not a leaf, recurse down yield from allPaths(node.left, fullPath) # left leaves if any yield from allPaths(node.right, fullPath) # right leaves if any else: yield fullPath # leaf node, return final path