Path Sum

+10

Ti viene dato un albero binario memorizzato nell'array tree in ordine per livelli e un numero targetSum. La radice si trova all'indice 0, i figli del nodo all'indice i si trovano agli indici 2*i+1 (sinistro) e 2*i+2 (destro), -1 indica una posizione vuota e l'array può terminare con ulteriori voci -1. Restituisci true se esiste un percorso dalla radice a una foglia i cui valori sommati danno targetSum, e false altrimenti. Una foglia è un nodo senza figli: entrambe le posizioni dei suoi figli sono vuote.

Funzione

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

treeinteger-array: l'albero binario in ordine per livelli, con -1 per una posizione vuota
targetSuminteger: il totale che un percorso dalla radice a una foglia deve raggiungere
Restituisceboolean: vero se qualche percorso dalla radice a una foglia somma fino a targetSum, falso altrimenti

Vincoli

1 ≤ tree.length ≤ 32767
Ogni tree[i] è -1 oppure un valore con 0 ≤ tree[i] ≤ 1000.
tree[0] non è mai -1, quindi l’albero ha almeno un nodo.
L'array potrebbe terminare con voci -1 aggiuntive dopo l'ultimo nodo.
Entrambi i figli di una posizione vuota sono vuoti a loro volta e la profondità è al massimo 14.
0 ≤ targetSum ≤ 15000

Esempi

Input: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Output: true
Spiegazione: Il percorso 3, 9, 2 (indici 0, 1, 4) dà come somma 14, e il 2 all'indice 4 è una foglia.

Input: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Output: false
Spiegazione: 3 + 9 = 12, ma il 9 ha un figlio, quindi nessun percorso termina lì. I tre percorsi dalla radice alla foglia danno come somma 14, 10 e 16, e nessuno di essi è 12.

Input: tree = [4, -1, -1]targetSum = 4
Output: true
Spiegazione: Entrambi i rami figli della radice sono vuoti, quindi la radice è una foglia a sé stante. Il percorso che contiene solo 4 ha una somma pari a 4.

+14 test nascosti all’invio

Per approfondire

Riesci a contare i percorsi la cui somma è targetSum quando un percorso può iniziare da qualsiasi nodo e terminare in qualsiasi nodo sotto di esso, e non solo andare dalla radice a una foglia?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La domanda riguarda percorsi completi, dalla radice fino a una foglia. Un totale parziale può raggiungere targetSum a metà percorso, in un nodo che ha ancora dei figli, ma questo non conta. Quindi porti la somma del percorso fino a quel punto a ogni nodo e la confronti con il target solo nelle foglie. La ricorsione porta questa somma come parametro; una pila la porta accanto a ogni nodo.

Ricorsione sulla somma rimanente

Intuizione

Per prima cosa, vediamo come spostarsi nell’array. Il nodo all’indice i ha il figlio sinistro all’indice 2*i+1 e il figlio destro all’indice 2*i+2. Un figlio esiste solo se il suo indice è all’interno dell’array e il valore corrispondente non è -1. In [3, 9, 6, -1, 2, 1, 7], la radice 3 ha figli agli indici 1 e 2, mentre il nodo 9 all’indice 1 ha uno spazio vuoto a sinistra all’indice 3 e il nodo 2 all’indice 4 a destra.

Ora vediamo l’idea. Un percorso la cui somma è targetSum inizia con il valore della radice, quindi il resto del percorso, che inizia da uno dei figli della radice, deve avere una somma pari a targetSum meno quel valore. È la stessa domanda su un albero più piccolo. Sottrai il valore di ogni nodo man mano che scendi. In una foglia il percorso termina, quindi la risposta è se non resta nulla.

Nel primo esempio la radice lascia 14 - 3 = 11, il nodo 9 lascia 2 e la foglia 2 lascia 0: true. Nel secondo esempio il nodo 9 lascia già 0, ma ha un figlio, quindi la ricerca continua e la sua foglia termina con -2. Ogni nodo viene visitato al massimo una volta: tempo O(n); lo stack delle chiamate contiene un frame per livello: O(h), al massimo 15 frame qui (una profondità di 14 conta gli archi sotto la radice).

Algoritmo

Scrivi walk(i, remaining) e sottrai tree[i] da remaining.
Se entrambi i posti dei figli di i sono vuoti (indice oltre la fine oppure -1), restituisci se remaining è 0.
Altrimenti restituisci true se walk su un figlio sinistro effettivo o su un figlio destro effettivo restituisce true.
Restituisci 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)

Ricerca in profondità con uno stack esplicito

Intuizione

La ricorsione conserva un numero per chiamata: quanto manca ancora al valore target. Puoi conservare personalmente un numero del genere, su uno stack accanto a ciascun nodo, ed eliminare le chiamate. Memorizza la somma del percorso dalla radice fino al nodo, nodo incluso. Inizia con (0, tree[0]) e assegna a ciascun figlio la somma del genitore più il valore del figlio.

Estrai una coppia. Se il nodo è una foglia e la sua somma è uguale a targetSum, hai finito. Altrimenti inserisci i suoi figli effettivi. Nel primo esempio, il lato destro viene estratto per primo dallo stack: le foglie 7 e 1 hanno rispettivamente 16 e 10. Poi viene estratta (1, 12) per il 9. Non è una foglia, quindi inserisce (4, 14), una foglia con la somma corretta.

Ogni nodo effettivo viene inserito una sola volta, quindi il tempo è O(n) e la ricerca si interrompe alla prima foglia corrispondente. Lo stack contiene i nodi fratelli in attesa lungo il percorso corrente, circa uno per livello, con uno spazio di O(h). Lo stesso ciclo funziona su un albero profondo basato su puntatori, in cui la ricorsione potrebbe esaurire lo stack.

Algoritmo

Inserisci (0, tree[0]) in uno stack.
Estrai una coppia (i, total) e controlla le posizioni dei figli 2*i+1 e 2*i+2.
Se nessuno dei due figli è reale e total è uguale a targetSum, restituisci true.
Inserisci ogni figlio reale c come (c, total + tree[c]).
Quando lo stack è vuoto, restituisci 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

Trappole e casi limite

Quasi tutti i bug in questo problema riguardano il punto in cui termina un percorso.

Confrontare la somma in ogni nodo. Nel secondo esempio 3 + 9 = 12 corrisponde al nodo 9, che ha un figlio, quindi la risposta è false. Confronta solo nei nodi foglia.
Considerare uno spazio vuoto per un figlio come la fine di un percorso. Se walk in uno spazio vuoto restituisce remaining == 0, il nodo 9 nel secondo esempio viene considerato una foglia tramite il suo spazio vuoto a sinistra. Un nodo è una foglia solo quando entrambi gli spazi sono vuoti.
Dimenticare il caso in cui c'è solo la radice. Un singolo nodo è una foglia, quindi [4] con targetSum = 4 è true, e lo è anche [0] con targetSum = 0.
Interrompere la ricerca quando il totale supera il target. Qui i valori non sono mai negativi, quindi in questo problema è sicuro, ma lo stesso codice dà risposte errate non appena un albero può contenere valori negativi.
Leggere oltre la fine. Una foglia vicino alla fine dell'array può avere indici dei figli oltre l'ultima posizione, perché l'array può terminare subito dopo l'ultimo nodo. Controlla l'indice prima di leggere tree[c].
Confondere l'offset in Lua e R, dove gli array iniziano da 1. Mantieni gli indici dei nodi a partire da 0 per il calcolo 2*i+1 e leggi tree[i + 1].

Domande frequenti4

Qual è la complessità temporale di Path Sum?

Ogni nodo viene visitato al massimo una volta, quindi la complessità temporale è O(n) e la ricerca può fermarsi alla prima foglia corrispondente. Lo spazio aggiuntivo è O(h) per il percorso esplorato, sotto forma di frame di chiamata o di elementi nel tuo stack.

Perché Path Sum controlla la somma solo nei nodi foglia?

Il problema richiede un percorso dalla radice a una foglia, e un percorso che termina in un nodo con figli non è un percorso di questo tipo. Verificare a ogni nodo restituisce true troppo spesso, per esempio quando il valore della sola radice è uguale al target ma la radice ha un figlio. Un nodo conclude un percorso solo quando entrambi i suoi nodi figli sono vuoti.

È possibile risolvere Path Sum con BFS?

Sì. Inserisci in una coda coppie composte da un nodo e dalla somma del suo percorso, invece che in una pila, e controlla ogni foglia man mano che viene estratta. Il tempo è ancora O(n), ma la coda può contenere un intero livello, circa la metà dei nodi di un albero completo, mentre una pila contiene circa un nodo per livello.

Come trovi tutti i percorsi la cui somma è uguale al valore obiettivo?

Mantieni l’elenco dei nodi del percorso corrente mentre scendi, copialo nella risposta a ogni foglia la cui somma corrisponde e rimuovi l’ultimo nodo quando risali. La visita rimane la stessa; cresce solo la gestione dei dati. Copiare i percorsi può costare più della visita stessa quando corrispondono molte foglie.

Python

def hasPathSum(tree, targetSum):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

true