Faça uma função que retorna a lista de caminhos da raiz até cada folha.

Passo 1

A gente precisa criar uma função que, dado o nó raiz de uma árvore binária, retorne todas as sequências de valores dos nós do caminho que vai da raiz até cada folha. O conteúdo aqui é travessia em profundidade (DFS) com backtracking para coletar caminhos.
Vamos usar uma lista externa chamada paths para guardar cada caminho completo. A cada recursão, vamos manter uma lista current_path com os valores visitados até o momento. No início, chamamos a função auxiliar dfs(node, current_path, paths) passando a raiz e listas vazias.

Passo 2

Na função auxiliar dfs, primeiro checamos se o nó é None. Se for, não fazemos nada (caso de parada). Se não, adicionamos node.val em current_path. Depois, se o nó não tem filho esquerdo nem direito, é uma folha: fazemos uma cópia de current_path e armazenamos em paths. Caso contrário, chamamos dfs recursivamente em node.left e node.right para explorar subárvores.
Após as chamadas recursivas, precisamos remover o último elemento de current_path (backtracking), para que, ao retornar ao pai, o caminho volte ao estado anterior. Assim, garantimos que cada ramo constrói seu próprio caminho corretamente.

Passo 3

Em termos de complexidade, cada nó é visitado exatamente uma vez, e em cada visita podemos copiar o caminho atual (no máximo da altura da árvore). Portanto, o tempo é O(N·H), onde N é o número de nós e H a altura da árvore, e o espaço usado pelo paths e pela pilha de recursão também fica em O(N·H).

Resposta

Vamos supor a definição de nó de árvore em Python

definicao da classe TreeNode:
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def todos_caminhos_da_raiz_ate_folhas(root):
paths = [] # lista que vai conter todos os caminhos
def dfs(node, current_path):
if node is None:
return
# inclui o valor do nó no caminho atual
current_path.append(node.val)
# se for folha, copia o caminho atual para paths
if node.left is None and node.right is None:
paths.append(list(current_path))
else:
# caso contrário, explora recursivamente subárvores
dfs(node.left, current_path)
dfs(node.right, current_path)
# backtracking: remove o nó atual para voltar ao estado anterior
current_path.pop()
# inicia DFS a partir da raiz
dfs(root, [])
return paths

Exemplo de uso:

1

/ \

2 3

/ \

4 5

todos_caminhos_da_raiz_ate_folhas(root) retornaria [[1,2,4],[1,3,5]]

Exercícios relacionados