Path Sum
Você recebe uma árvore binária armazenada no array tree em ordem por nível e um número targetSum. A raiz fica no índice 0, os filhos do nó no índice i ficam em 2*i+1 (à esquerda) e 2*i+2 (à direita), -1 marca uma posição vazia, e o array pode terminar com entradas extras -1. Retorne true se algum caminho da raiz até uma folha tiver valores cuja soma seja igual a targetSum, e false caso contrário. Uma folha é um nó cujas duas posições de filho estão vazias.
Função
- treeinteger-array
- a árvore binária em ordem por nível, com -1 para um espaço vazio
- targetSuminteger
- o total que um caminho da raiz até uma folha deve atingir
- Retornaboolean
- verdadeiro se algum caminho da raiz até uma folha somar targetSum, falso caso contrário
Restrições
1 ≤ tree.length ≤ 32767- Cada
tree[i]é-1ou um valor com0 ≤ tree[i] ≤ 1000. tree[0]nunca é-1, então a árvore tem pelo menos um nó.- A matriz pode terminar com entradas extras
-1após o último nó. - Ambos os filhos de um espaço vazio também estão vazios, e a profundidade é no máximo
14. 0 ≤ targetSum ≤ 15000
Exemplos
- Entrada
- tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
- Saída
- true
- Explicação
- O caminho
3,9,2(índices0,1,4) soma14, e o2no índice4é uma folha.
- Entrada
- tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
- Saída
- false
- Explicação
3 + 9 = 12, mas o9tem um filho, então nenhum caminho termina ali. Os três caminhos da raiz até uma folha somam14,10e16, e nenhum deles é12.
- Entrada
- tree = [4, -1, -1]targetSum = 4
- Saída
- true
- Explicação
- Ambos os espaços dos filhos da raiz estão vazios, então a raiz é uma folha por si só. O caminho que contém apenas
4soma4.
Para ir além
Você consegue contar os caminhos cuja soma é targetSum se um caminho puder começar em qualquer nó e terminar em qualquer nó abaixo dele?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Desça a partir da raiz e mantenha um total acumulado. Onde você pode comparar esse total com
targetSum?Somente em uma folha, um nó cujos dois espaços para filhos estão vazios. Um nó com um filho não encerra um caminho, mesmo que o total já corresponda. Leve a soma do caminho até agora para cada filho.
Mantenha uma pilha de pares: o índice de um nó e a soma da raiz até esse nó. Remova um par; se o nó for uma folha e a soma for igual a
targetSum, retornetrue. Caso contrário, adicione cada filho existente com a soma acrescida do valor do filho.
Solução
Contam apenas os caminhos completos, da raiz até uma folha. A soma acumulada pode atingir targetSum em um nó que ainda tem filhos, o que não conta. Portanto, leve a soma do caminho até cada nó, como parâmetro ou em uma pilha, e compare-a com o alvo apenas nas folhas.
Recursão sobre a soma restante
Intuição
Um caminho cuja soma seja targetSum começa com o valor da raiz, então o restante dele, que começa em um dos filhos da raiz, deve somar targetSum menos esse valor. Essa é a mesma pergunta em uma árvore menor. Subtraia o valor de cada nó ao descer; em uma folha, o caminho termina, então a resposta é se não resta nada.
No primeiro exemplo, a raiz deixa 14 - 3 = 11, o 9 deixa 2 e a folha 2 deixa 0. No segundo, o 9 já deixa 0, mas tem um filho, então a busca continua. Cada nó é visitado uma vez, tempo O(n), e a pilha de chamadas contém um quadro por nível, no máximo 15.
Algoritmo
- Escreva
walk(i, remaining)e subtraiatree[i]deremaining. - Se as posições dos dois filhos de
iestiverem vazias (índice além do final ou-1), retorne seremainingé0. - Caso contrário, retorne
truesewalkem um filho esquerdo existente ou em um filho direito existente retornartrue. - Retorne
walk(0, targetSum).
def hasPathSum(tree, targetSum):
n = len(tree)
def walk(i, remaining):
# remaining is what the path still needs once it reaches node i.
remaining -= tree[i]
left, right = 2 * i + 1, 2 * i + 2
has_left = left < n and tree[left] != -1
has_right = right < n and tree[right] != -1
if not has_left and not has_right:
return remaining == 0 # a leaf: the path ends here
return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))
return walk(0, targetSum)Busca em profundidade com uma pilha explícita
Intuição
A recursão mantém um número por chamada. Em vez disso, mantenha-o você mesmo, em uma pilha ao lado de cada nó: a soma do caminho da raiz até esse nó. Comece com (0, tree[0]); cada filho recebe a soma do pai mais o próprio valor. Retire um par da pilha. Se o nó for uma folha com soma targetSum, você terminou; caso contrário, empilhe os filhos reais dele.
Cada nó real é empilhado uma vez, tempo O(n), e a pilha mantém cerca de um irmão aguardando por nível, O(h). O mesmo loop funciona em uma árvore profunda baseada em ponteiros, na qual a recursão poderia esgotar a pilha.
Algoritmo
- Empilhe
(0, tree[0])em uma pilha. - Retire um par
(i, total)e verifique as posições dos filhos2*i+1e2*i+2. - Se nenhum dos filhos for real e
totalfor igual atargetSum, retornetrue. - Empilhe cada filho real
ccomo(c, total + tree[c]). - Quando a pilha estiver vazia, retorne
false.
def hasPathSum(tree, targetSum):
n = len(tree)
stack = [(0, tree[0])] # (node index, sum of the path from the root to it)
while stack:
i, total = stack.pop()
left, right = 2 * i + 1, 2 * i + 2
has_left = left < n and tree[left] != -1
has_right = right < n and tree[right] != -1
if not has_left and not has_right and total == targetSum:
return True # a leaf whose path adds up
if has_left:
stack.append((left, total + tree[left]))
if has_right:
stack.append((right, total + tree[right]))
return False
Armadilhas e casos extremos
- Comparar a soma em cada nó. No segundo exemplo,
3 + 9 = 12corresponde ao nó9, que tem um filho, então a resposta éfalse. - Deixar que um espaço vazio de filho encerre um caminho. Assim, o
9no segundo exemplo encerra um caminho pelo seu espaço vazio à esquerda. - Esquecer a raiz isolada. Um único nó é uma folha, então
[4]com o alvo4étrue, assim como[0]com o alvo0. - Ler além do fim do array. Uma folha perto do fim pode ter índices de filhos além da última entrada.
- Confundir o deslocamento em Lua e R. Mantenha os índices dos nós baseados em 0 para
2*i+1e leiatree[i + 1].
Perguntas frequentes3
Qual é a complexidade de tempo de Path Sum?
O(n): cada nó é visitado no máximo uma vez, e a busca pode parar na primeira folha que corresponde. O espaço extra é O(h) para o caminho que está sendo explorado, seja como quadros de chamada ou como entradas na sua própria pilha.
Path Sum pode ser resolvido com BFS?
Sim. Coloque pares de um nó e da soma do caminho dele em uma fila em vez de uma pilha, e verifique cada folha à medida que ela sai. O tempo continua sendo O(n), mas a fila pode armazenar um nível inteiro, cerca de metade dos nós de uma árvore completa, enquanto uma pilha armazena cerca de um nó por nível.
Como encontrar todos os caminhos cuja soma é igual ao valor-alvo?
Mantenha a lista de nós do caminho atual enquanto desce, copie-a para a resposta em cada folha cuja soma corresponda e remova o último nó ao voltar. A travessia permanece a mesma. Copiar os caminhos pode custar mais do que a travessia quando muitas folhas correspondem.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def hasPathSum(tree, targetSum):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
tree = [3, 9, 6, -1, 2, 1, 7] targetSum = 14
Saída Esperada
true