Path Sum

Q: Qual è la complessità temporale di Path Sum?

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

FacileVisita di alberi

+10

Ti viene fornito 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 elementi -1. Restituisci true se esiste un percorso dalla radice a una foglia i cui valori sommano a targetSum, altrimenti restituisci false. Una foglia è un nodo le cui due posizioni dei figli sono entrambe vuote.

Funzione

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

treeinteger-array: l'albero binario in ordine di livello, con -1 per una posizione vuota
targetSuminteger: il totale che un percorso dalla radice alla foglia deve raggiungere
Restituisceboolean: vero se qualche percorso dalla radice alla foglia ha somma 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 può terminare con elementi -1 aggiuntivi dopo l'ultimo nodo.
Entrambi i figli di una posizione vuota sono vuoti anch’essi 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 risultato 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 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 posti dei figli della radice sono vuoti, quindi la radice è una foglia a sé stante. Il percorso che contiene solo 4 dà come somma 4.

Per approfondire

Riesci a contare i percorsi la cui somma è targetSum, se un percorso può iniziare da qualsiasi nodo e terminare in qualsiasi nodo al di sotto di esso?

Suggerimenti

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

0 di 3 aperti

Soluzione

Contano solo i percorsi completi, dalla radice fino a una foglia. Un totale parziale può raggiungere targetSum in un nodo che ha ancora dei figli, ma questo non conta. Quindi porta la somma del percorso fino a ogni nodo, come parametro o su uno stack, e confrontala con il valore obiettivo solo nelle foglie.

Ricorsione sulla somma rimanente

Intuizione

Un percorso che somma targetSum inizia con il valore della radice, quindi il resto del percorso, che inizia da uno dei figli della radice, deve sommare targetSum meno quel valore. È la stessa domanda su un albero più piccolo. Sottrai il valore di ciascun 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 9 lascia 2 e la foglia 2 lascia 0. Nel secondo, il 9 lascia già 0, ma ha un figlio, quindi la ricerca continua. Ogni nodo viene visitato una volta: tempo O(n), e lo stack delle chiamate contiene un frame per livello, al massimo 15.

Algoritmo

Scrivi walk(i, remaining) e sottrai tree[i] da remaining.
Se entrambe le posizioni dei figli di i sono vuote (indice oltre la fine oppure -1), restituisci se remaining è 0.
Altrimenti restituisci true se walk su un figlio sinistro reale o su un figlio destro reale 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 una pila esplicita

Intuizione

La ricorsione mantiene un numero per chiamata. Mantienilo tu invece, su uno stack accanto a ciascun nodo: la somma del percorso dalla radice fino a quel nodo. Inizia con (0, tree[0]); ogni figlio riceve la somma del genitore più il proprio valore. Estrai una coppia. Se il nodo è una foglia con somma targetSum, hai finito; altrimenti inserisci i suoi figli effettivi.

Ogni nodo effettivo viene inserito una sola volta, O(n) di tempo, e lo stack contiene circa un fratello in attesa per livello, O(h). Lo stesso ciclo funziona su un albero profondo basato su puntatori, dove 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

Confrontare la somma in ogni nodo. Nel secondo esempio 3 + 9 = 12 corrisponde al nodo 9, che ha un figlio, quindi la risposta è false.
Lasciare che uno spazio vuoto per un figlio termini un percorso. In questo modo, il 9 nel secondo esempio termina un percorso attraverso il suo spazio vuoto a sinistra.
Dimenticare la radice da sola. Un nodo singolo è una foglia, quindi [4] con target 4 è true, e lo è anche [0] con target 0.
Leggere oltre la fine dell’array. Una foglia vicino alla fine può avere indici dei figli oltre l’ultima voce.
Confondere l’offset in Lua e R. Mantieni gli indici dei nodi a base 0 per 2*i+1 e leggi tree[i + 1].

Domande frequenti3

Qual è la complessità temporale di Path Sum?

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

Si può risolvere Path Sum con la BFS?

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

Come trovi ogni percorso la cui somma è uguale all’obiettivo?

Man mano che scendi, mantieni l’elenco dei nodi nel percorso corrente, copialo nella risposta in corrispondenza di ogni foglia la cui somma corrisponde e rimuovi l’ultimo nodo quando risali. La visita rimane la stessa. Copiare i percorsi può costare più della visita quando corrispondono molte foglie.

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

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

true