Soma de Caminhos e Ancestral Comum Mais Baixo
Resolva soma de caminhos da raiz às folhas, soma de todos os caminhos e ancestral comum mais baixo em uma árvore binária geral usando descida recursiva.
Soma de Caminhos e Ancestral Comum Mais Baixo é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Soma do caminho da raiz à folha
O problema da soma do caminho pergunta se existe algum caminho da raiz à folha cuja soma seja igual a um alvo. Passe o alvo restante pela recursão, subtraindo o valor de cada nó. Em uma folha, verifique se o valor restante é igual ao valor da folha. Isso evita manter uma lista explícita do caminho, economiza espaço e mantém a solução simples. Caso-limite: uma árvore vazia não tem caminhos; portanto, retorne False imediatamente.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right: # leaf
return root.val == target
remain = target - root.val
return (has_path_sum(root.left, remain) or
has_path_sum(root.right, remain))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5->4->11->2Todos os caminhos da raiz à folha
Para enumerar todos os caminhos, mantenha uma lista do caminho atual. Em cada chamada recursiva, acrescente o valor do nó atual, faça a recursão nos filhos e então faça pop ao retornar (retrocesso). Em uma folha, registre uma cópia (list(path)) do caminho atual. Esse padrão — escolher, recorrer, desfazer a escolha — é a base do retrocesso em árvores.
def all_path_sums(root, target):
results = []
def dfs(node, path, remaining):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
results.append(list(path)) # snapshot
else:
dfs(node.left, path, remaining - node.val)
dfs(node.right, path, remaining - node.val)
path.pop() # backtrack
dfs(root, [], target)
return results
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22)) # [[5,4,11,2]]Soma de caminhos III: qualquer caminho, qualquer nó
Soma de caminhos III (LeetCode #437) conta os caminhos cuja soma é igual a um alvo, podendo o caminho começar e terminar em qualquer lugar (não apenas na raiz e em uma folha). A força bruta tem complexidade O(n²): execute um DFS a partir de cada nó. A abordagem ideal, de complexidade O(n), usa uma tabela de dispersão de somas prefixadas: acompanhe a soma acumulada e conte quantas vezes current_sum - target apareceu anteriormente, seguindo a mesma ideia da abordagem de soma de subvetores.
def path_sum_iii(root, target):
prefix_counts = {0: 1}
def dfs(node, running_sum):
if not node:
return 0
running_sum += node.val
count = prefix_counts.get(running_sum - target, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
count += dfs(node.left, running_sum)
count += dfs(node.right, running_sum)
prefix_counts[running_sum] -= 1 # backtrack
return count
return dfs(root, 0)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8)) # 3O que é o menor ancestral comum?
O menor ancestral comum (LCA) de dois nós p e q em uma árvore binária é o nó mais profundo que tem p e q como descendentes (um nó pode ser descendente de si mesmo). O LCA aparece em problemas como “distância entre dois nós”, “caminho entre dois nós” e consultas de intervalo em BST. Compreender o LCA é essencial para resolver problemas intermediários de árvores.
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
# LCA(5, 1) = 3 (root)
# LCA(5, 4) = 5 (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')Algoritmo recursivo de LCA
A elegante solução recursiva para LCA retorna o primeiro nó que é p ou q, ou que tem ambos em suas subárvores. Se o nó atual for p ou q, retorne-o. Caso contrário, faça a recursão à esquerda e à direita. Se ambos os lados retornarem valores não nulos, o nó atual será o LCA. Se apenas um lado retornar um valor não nulo, propague esse resultado para cima. Essa solução tem complexidade de tempo O(n) e de espaço O(h).
def lowest_common_ancestor(root, p, q):
# Base case: empty or found one of the targets
if not root or root == p or root == q:
return root
# Search both subtrees
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found something, this node is the LCA
if left and right:
return root
# Otherwise, return whichever side found something
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 3LCA quando um nó pode ser seu próprio ancestral
Um caso-limite importante: se p for ancestral de q (ou vice-versa), o LCA será o próprio p. O algoritmo recursivo trata isso automaticamente: quando chega a p, retorna p imediatamente, sem examinar as subárvores de p. O pai verá que um lado retornou p e o outro retornou nulo, então propagará p para cima como o LCA. Verifique sempre esse caso em seus testes ao implementar LCA.
# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)
p = root.left # node 5
q = root.left.left # node 6
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 5 (p itself is the LCA)LCA com ponteiros para o pai
Se cada nó tiver um ponteiro para o pai, o LCA se reduz ao problema da “interseção de duas listas encadeadas”. Reúna os ancestrais de p em um conjunto e, em seguida, suba a partir de q até encontrar um nó nesse conjunto. Essa abordagem, com complexidade de tempo O(h) e espaço O(h), é comum em entrevistas de projeto de sistemas, nas quais você controla a estrutura dos nós e pode armazenar referências aos pais.
class NodeWithParent:
def __init__(self, val, parent=None):
self.val = val
self.parent = parent
self.left = None
self.right = None
def lca_with_parent(p, q):
ancestors = set()
# Collect all ancestors of p
node = p
while node:
ancestors.add(node)
node = node.parent
# Walk up from q until we hit a known ancestor
node = q
while node:
if node in ancestors:
return node
node = node.parent
return None
print('With parent pointers: O(h) time and space')LCA em uma árvore de busca binária
Em uma BST, o LCA é mais simples porque a propriedade de ordenação informa qual subárvore contém cada nó. Se p e q forem menores que o nó atual, o LCA estará na subárvore esquerda. Se ambos forem maiores, o LCA estará na subárvore direita. Caso contrário, o nó atual os separa, portanto ele é o LCA. Isso reduz o problema a O(log n) em BSTs balanceadas.
def lca_bst(root, p, q):
if not root:
return None
if p.val < root.val and q.val < root.val:
return lca_bst(root.left, p, q) # both in left
if p.val > root.val and q.val > root.val:
return lca_bst(root.right, p, q) # both in right
return root # split point = LCA
# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
print('BST LCA: O(log n) for balanced trees')Distância entre dois nós
A distância entre dois nós em uma árvore é igual ao número de arestas no caminho que os conecta. Ela pode ser calculada diretamente a partir do LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Encontre primeiro o LCA e, em seguida, conte a profundidade de cada nó. Com uma função auxiliar adequada, isso tem complexidade de tempo O(n) e espaço O(h).
def find_depth(root, target, depth=0):
if not root:
return -1
if root == target:
return depth
left = find_depth(root.left, target, depth + 1)
if left != -1:
return left
return find_depth(root.right, target, depth + 1)
def node_distance(root, p, q):
lca = lowest_common_ancestor(root, p, q)
# depth from LCA to p and q
dp = find_depth(lca, p)
dq = find_depth(lca, q)
return dp + dq
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right)) # 2Caminho de soma máxima da raiz à folha
O caminho de soma máxima da raiz à folha acompanha a soma acumulada desde a raiz até o nó atual. Nas folhas, compare-a com um máximo global. Esse é um DFS de pré-ordem no qual a soma do caminho atual é passada como parâmetro. Diferentemente da soma máxima de caminhos genérica, esta versão é restrita a caminhos da raiz à folha, portanto é mais simples: não é necessário considerar caminhos arbitrários entre nós.
def max_root_to_leaf_sum(root):
if not root:
return float('-inf')
best = [float('-inf')]
def dfs(node, running):
running += node.val
if not node.left and not node.right: # leaf
best[0] = max(best[0], running)
return
if node.left:
dfs(node.left, running)
if node.right:
dfs(node.right, running)
dfs(root, 0)
return best[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root)) # 1+2+5 = 8Soma dos números da raiz à folha
Somar números da raiz à folha (LeetCode #129) trata cada caminho da raiz à folha como um número decimal (por exemplo, o caminho 1→2→3 representa o número 123) e pede a soma desses números. Construa o número passando current_number * 10 + node.val pela recursão. Em cada folha, adicione o número completo ao total. Este é um exemplo claro de DFS de pré-ordem que passa um estado acumulado para baixo.
def sum_numbers(root):
def dfs(node, num):
if not node:
return 0
num = num * 10 + node.val
if not node.left and not node.right: # leaf
return num
return dfs(node.left, num) + dfs(node.right, num)
return dfs(root, 0)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root)) # 12 + 13 = 25
root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2)) # 495 + 491 + 40 = 1026Verificação rápida
Verifique sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: variantes de soma de caminhos (da raiz à folha, todos os caminhos e soma de caminhos III com somas prefixadas), o menor ancestral comum usando uma divisão recursiva elegante e o LCA em BST em O(log n) usando a propriedade de ordenação. A seguir, começaremos a estudar árvores de busca binária com operações de inserção e busca.
Perguntas Frequentes
A aula “Soma de Caminhos e Ancestral Comum Mais Baixo” é grátis?
Sim — o texto completo de “Soma de Caminhos e Ancestral Comum Mais Baixo” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Soma de Caminhos e Ancestral Comum Mais Baixo”?
Resolva soma de caminhos da raiz às folhas, soma de todos os caminhos e ancestral comum mais baixo em uma árvore binária geral usando descida recursiva. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Soma de Caminhos e Ancestral Comum Mais Baixo”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Classe TreeNode e BFS por Níveis
- DFS em Ordem, Pré-Ordem e Pós-Ordem
- Diâmetro, Altura e Árvores Balanceadas
- Soma de Caminhos e Ancestral Comum Mais Baixo