Soma alvo da raiz até a folha
A missão
Problema
Dada uma árvore binária e um número alvo, decida se existe algum caminho da raiz até uma folha cujos valores somem exatamente o alvo. Uma folha é um nó sem filhos, então um caminho sempre precisa terminar na base da árvore. Os valores podem ser negativos.
Exemplos
Input: tree = 5, left 4 with left child 11 having children 7 and 2,
right 8 with children 13 and 4; target = 22
Output: True
Por quê: o caminho 5, 4, 11, 2 soma 22
Input: tree = 1 with a single left child 2; target = 1
Output: False
Por quê: a raiz não é uma folha, então o caminho não pode parar nela
Input: tree = empty; target = 0
Output: False
Por quê: edge case: uma árvore vazia não tem nenhum caminho da raiz até uma folha
Dicas
0 / 3
A árvore divide a pergunta em duas perguntas menores do mesmo tipo, uma por filho, e a resposta é sim quando qualquer uma delas diz sim.
Em vez de somar os valores na volta, subtraia cada valor do alvo enquanto desce, para que um filho só enxergue o quanto ainda falta.
Desça a partir da raiz carregando o valor restante. Em uma folha, responda sim exatamente quando o restante for igual ao valor dessa folha. Em um galho ausente, responda não, para que um nó com um só filho nunca seja confundido com um ponto de parada.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(h)
Restrições
- values may be negative
- a path must end at a leaf
Solução
Carregar o valor restante para baixo transforma a pergunta em cada nó na mesma pergunta sobre uma árvore menor, então uma única recursão cobre a busca inteira. O caso do galho ausente precisa responder não em vez de checar o restante; caso contrário, um nó com um único filho seria tratado como um ponto final válido. Uma folha responde comparando o restante com o próprio valor, e os dois filhos são combinados com um OR em curto-circuito. O tempo é O(n) no pior caso, e o espaço é O(h) para a pilha de chamadas (call stack).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def has_path_sum(node, target):
if node is None:
return False # an absent branch is not a stopping point
rest = target - node.val
if node.left is None and node.right is None:
return rest == 0 # only a leaf may close the path
return has_path_sum(node.left, rest) or has_path_sum(node.right, rest)
print(has_path_sum(T(5, T(4, T(11, T(7), T(2))), T(8, T(13), T(4))), 22)) # -> True
print(has_path_sum(T(1, T(2)), 1)) # -> False
print(has_path_sum(None, 0)) # -> FalseTravou na ideia, e não no código? Variações de soma de caminho explica isso.