Path Sum

Q: Qual é a complexidade de tempo de Path Sum?

Cada nó é visitado no máximo uma vez, então o tempo é O(n) , e a busca pode parar na primeira folha que corresponder. O espaço extra é O(h) para o caminho que está sendo explorado, seja em quadros de chamada, seja em entradas na sua própria pilha.

FácilPercurso em árvores

+10

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 (esquerdo) e 2*i+2 (direito), -1 marca uma posição vazia, e o array pode terminar com entradas extras de -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ó sem filhos: as posições de ambos os seus filhos estão vazias.

Função

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: a árvore binária em ordem por nível, com -1 para uma posição vazia
targetSuminteger: o total que um caminho da raiz até a folha deve atingir
Retornaboolean: verdadeiro se algum caminho da raiz até uma folha soma targetSum, falso caso contrário

Restrições

1 ≤ tree.length ≤ 32767
Cada tree[i] é -1 ou um valor com 0 ≤ tree[i] ≤ 1000.
tree[0] nunca é -1, então a árvore tem pelo menos um nó.
O array pode terminar com entradas -1 extras apó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 (índices 0, 1, 4) soma 14, e o 2 no índice 4 é uma folha.

Entrada: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Saída: false
Explicação: 3 + 9 = 12, mas o 9 tem um filho, então nenhum caminho termina ali. Os três caminhos da raiz até uma folha somam 14, 10 e 16, e nenhum deles é 12.

Entrada: tree = [4, -1, -1]targetSum = 4
Saída: true
Explicação: Ambas as posições dos filhos da raiz estão vazias, então a raiz é uma folha por si só. O caminho que contém apenas 4 soma 4.

+14 testes ocultos ao enviar

Para ir além

Você consegue contar os caminhos cuja soma é igual a targetSum, quando um caminho pode começar em qualquer nó e terminar em qualquer nó abaixo dele, e não apenas ir da raiz até uma folha?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A pergunta é sobre caminhos completos, da raiz até uma folha. A soma acumulada pode chegar a targetSum no meio do caminho, em um nó que ainda tem filhos, e isso não conta. Portanto, você leva a soma do caminho até então para cada nó e a compara com o alvo somente nas folhas. A recursão carrega essa soma como parâmetro; uma pilha a carrega junto a cada nó.

Recursão na soma restante

Intuição

Primeiro, como percorrer o array. O nó no índice i tem o filho esquerdo no índice 2*i+1 e o filho direito no índice 2*i+2. Um filho só existe se o índice estiver dentro do array e o valor nessa posição não for -1. Em [3, 9, 6, -1, 2, 1, 7], a raiz 3 tem filhos nos índices 1 e 2, e o 9 no índice 1 tem um espaço vazio à esquerda no índice 3 e o 2 no índice 4 à direita.

Agora, a ideia. Um caminho cuja soma é targetSum começa com o valor da raiz, então o restante do caminho, 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 sobrou nada.

No primeiro exemplo, a raiz deixa 14 - 3 = 11, o 9 deixa 2 e a folha 2 deixa 0: true. No segundo exemplo, o 9 já deixa 0, mas tem um filho, então a busca continua, e sua folha termina em -2. Cada nó é visitado no máximo uma vez, tempo O(n), e a pilha de chamadas mantém um quadro por nível, O(h), no máximo 15 quadros aqui (uma profundidade de 14 conta as arestas abaixo da raiz).

Algoritmo

Escreva walk(i, remaining) e subtraia tree[i] de remaining.
Se os dois espaços dos filhos de i estiverem vazios (índice além do fim ou -1), retorne se remaining é 0.
Caso contrário, retorne true se walk em um filho esquerdo real ou em um filho direito real retornar true.
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: quanto ainda falta para atingir o alvo. Você pode manter esse número por conta própria, em uma pilha ao lado de cada nó, e eliminar as chamadas. Armazene a soma do caminho da raiz até o nó, incluindo o próprio nó. Comece com (0, tree[0]) e atribua a cada filho a soma do pai mais o valor do próprio filho.

Retire um par da pilha. Se o nó for uma folha e sua soma for igual a targetSum, você terminou. Caso contrário, empilhe seus filhos existentes. No primeiro exemplo, o lado direito sai primeiro da pilha: as folhas 7 e 1 carregam 16 e 10. Em seguida, (1, 12) para o 9 é retirado. Como não é uma folha, ele empilha (4, 14), uma folha com a soma correta.

Cada nó existente é empilhado uma vez, então o tempo é O(n), e a busca para na primeira folha correspondente. A pilha contém os irmãos que aguardam ao longo do caminho atual, cerca de um por nível, usando espaço O(h). O mesmo laço funciona em uma árvore profunda baseada em ponteiros, na qual a recursão poderia ficar sem espaço na pilha.

Algoritmo

Coloque (0, tree[0]) em uma pilha.
Retire um par (i, total) e verifique as posições dos filhos 2*i+1 e 2*i+2.
Se nenhum dos filhos existir e total for igual a targetSum, retorne true.
Coloque cada filho existente c como (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

Quase todos os bugs neste problema têm a ver com onde um caminho termina.

Comparar a soma em cada nó. No segundo exemplo, 3 + 9 = 12 corresponde ao valor no 9, que tem um filho, então a resposta é false. Compare apenas nas folhas.
Tratar um espaço de filho vazio como o fim de um caminho. Se walk em um espaço vazio retornar remaining == 0, o 9 no segundo exemplo será contado como uma folha por causa do espaço vazio à esquerda. Um nó só é uma folha quando ambos os espaços estão vazios.
Esquecer apenas a raiz. Um único nó é uma folha, então [4] com targetSum = 4 é true, assim como [0] com targetSum = 0.
Interromper a busca quando o total ultrapassa o alvo. Os valores nunca são negativos aqui, então isso é seguro neste problema, mas o mesmo código dá respostas erradas assim que uma árvore pode conter valores negativos.
Ler além do fim. Uma folha perto do fim do array pode ter índices de filhos além da última entrada, porque o array pode terminar logo após o último nó. Verifique o índice antes de ler tree[c].
Confundir o deslocamento em Lua e R, onde os arrays começam em 1. Mantenha os índices dos nós começando em 0 para a operação aritmética 2*i+1 e leia tree[i + 1].

Perguntas frequentes4

Qual é a complexidade de tempo de Path Sum?

Cada nó é visitado no máximo uma vez, então o tempo é O(n), e a busca pode parar na primeira folha que corresponder. O espaço extra é O(h) para o caminho que está sendo explorado, seja em quadros de chamada, seja em entradas na sua própria pilha.

Por que Path Sum verifica a soma apenas nos nós folha?

O problema pede um caminho da raiz até uma folha, e um caminho que para em um nó com filhos não é um deles. Verificar em cada nó retorna true com muita frequência, por exemplo, quando apenas o valor da raiz é igual ao alvo, mas a raiz tem um filho. Um nó só encerra um caminho quando os dois espaços para filhos estão vazios.

O Path Sum pode ser resolvido com BFS?

Sim. Coloque pares de um nó e da soma do caminho até ele em uma fila, em vez de uma pilha, e verifique cada folha quando ela sair. O tempo ainda é O(n), mas a fila pode conter um nível inteiro, cerca de metade dos nós de uma árvore completa, enquanto uma pilha contém cerca de um nó por nível.

Como encontrar todos os caminhos cuja soma é igual ao valor-alvo?

Mantenha a lista de nós no caminho atual enquanto avança, copie-a para a resposta em cada folha cuja soma corresponda e remova o último nó ao voltar. A travessia permanece igual; apenas o controle do caminho aumenta. Copiar os caminhos pode custar mais do que a própria travessia quando muitas folhas correspondem.

Python

def hasPathSum(tree, targetSum):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

Esperado

true