Maximum Depth of Binary Tree

Q: Qual è la complessità temporale della profondità massima di un albero binario?

Ogni approccio visita ogni nodo una volta, quindi il tempo è O(n) . Le versioni in profondità usano O(h) di spazio aggiuntivo per il percorso corrente, dove h è la profondità. La versione in ampiezza usa O(w) per il livello più ampio, che contiene circa la metà dei nodi in un albero completo.

Q: Dovresti usare DFS o BFS per calcolare la profondità massima di un albero binario?

Entrambi hanno una complessità temporale di O(n) . La ricerca in profondità è più breve da scrivere e usa una quantità di memoria proporzionale alla profondità, il che la rende adatta agli alberi larghi e poco profondi. La ricerca in ampiezza conta direttamente i livelli e usa una quantità di memoria proporzionale al livello più ampio, il che la rende adatta agli alberi profondi e stretti. Per trovare la profondità minima, vince la BFS perché può fermarsi alla prima foglia.

Q: Qual è la differenza tra la profondità e l'altezza di un albero binario?

La profondità di un nodo conta i passaggi dalla radice fino a esso; l’altezza conta i passaggi da esso fino alla foglia più profonda. La profondità massima dell’albero è uguale all’altezza della radice. Questo problema conta i nodi, quindi un singolo nodo ha profondità 1 ; contando gli archi si ottiene un valore inferiore di uno.

FacileVisita di alberi

+10

Ti viene fornito un albero binario memorizzato nell'array tree in ordine per livello. 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 voci -1 aggiuntive. Restituisci la profondità massima dell'albero: il numero di nodi sul percorso più lungo dalla radice fino a una foglia.

Funzione

maxDepth(tree: integer-array) → integer

treeinteger-array: l’albero binario in ordine per livelli, con -1 per una posizione vuota
Restituisceinteger: il numero di nodi nel percorso più lungo dalla radice a una foglia

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 voci -1 aggiuntive dopo l'ultimo nodo.
Entrambi i figli di uno spazio vuoto sono vuoti a loro volta e la profondità è al massimo 14.

Esempi

Input: tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Output: 4
Spiegazione: Il percorso più lungo è 5, 8, 3, 6 (indici 0, 1, 4, 9), che contiene 4 nodi. Il percorso che passa per 1 si ferma dopo 2 nodi.

Input: tree = [7, -1, -1]
Output: 1
Spiegazione: Le due voci -1 sono gli slot vuoti dei figli della radice. La radice da sola è un percorso di un nodo, quindi la profondità è 1, non 0.

Input: tree = [2, -1, 9, -1, -1, -1, 4]
Output: 3
Spiegazione: La radice 2 non ha un figlio sinistro. Il suo figlio destro 9 all'indice 2 ha 4 all'indice 6 come figlio destro: un percorso di 3 nodi.

Per approfondire

Come restituiresti i valori di un percorso radice-foglia più lungo e anche la sua lunghezza? Se più percorsi hanno la stessa lunghezza, quale restituiresti?

Suggerimenti

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

0 di 3 aperti

Soluzione

La profondità è determinata dal ramo più lungo e non puoi sapere quale sia senza visitare ogni nodo. Quindi ti serve un attraversamento completo che determini a quale profondità si trova ogni nodo. La ricorsione, una ricerca in ampiezza per livelli e una ricerca in profondità con uno stack personalizzato lo fanno in un solo passaggio.

Ricorsione sui due sottoalberi

Intuizione

Una posizione figlio è reale quando il suo indice è all’interno dell’array e il suo valore non è -1. Il percorso più profondo attraverso un nodo scende nel suo sottoalbero più profondo, quindi la profondità all’indice i è 1 per il nodo più il maggiore tra le profondità in 2*i+1 e 2*i+2. Una posizione vuota ha profondità 0, che termina la ricorsione. Una foglia ottiene 1 + max(0, 0) = 1, e i valori risalgono fino alla radice.

Ogni nodo viene visitato una volta. Lo stack delle chiamate contiene un frame per ogni livello del percorso corrente, O(h), al massimo 14 in questo caso.

Algoritmo

Scrivi depth(i): se i è oltre la fine dell'array oppure tree[i] è -1, restituisci 0.
Altrimenti restituisci 1 + max(depth(2*i+1), depth(2*i+2)).
Restituisci depth(0).

def maxDepth(tree):
    def depth(i):
        # An index past the end or a -1 is an empty spot: depth 0.
        if i >= len(tree) or tree[i] == -1:
            return 0
        return 1 + max(depth(2 * i + 1), depth(2 * i + 2))

    return depth(0)

Ricerca in ampiezza, livello per livello

Intuizione

La profondità massima è il numero di livelli, quindi puoi contare i livelli invece di seguire i percorsi. Una coda visita i nodi in ordine di livello. Prima di ogni gruppo, leggi la dimensione della coda: quei nodi corrispondono esattamente a un livello, perché i figli che aggiungi durante il gruppo si accodano dietro di loro. Ogni gruppo aggiunge 1 alla profondità. Nel primo esempio i gruppi sono [5], [8, 1], [3] e [6], quindi la risposta è 4.

La coda contiene un livello alla volta, O(w) per il livello più largo. In un albero completo di profondità 14, quel livello contiene 8192 dei 16383 nodi.

Algoritmo

Inserisci l’indice radice 0 in una coda e imposta depth = 0.
Finché la coda non è vuota, aggiungi 1 a depth e leggi la dimensione della coda.
Estrai quel numero di indici. Per ciascuno, inserisci in coda gli indici dei figli 2*i+1 e 2*i+2 che si trovano nell’array e non sono -1.
Quando la coda è vuota, restituisci depth.

from collections import deque


def maxDepth(tree):
    n = len(tree)
    queue = deque([0])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):  # exactly the nodes of this level
            i = queue.popleft()
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
    return depth

Ricerca in profondità con uno stack esplicito

Intuizione

Conserva il tuo stack di coppie, un indice del nodo e la sua profondità, poiché nient'altro ricorda quanto in profondità si trovi un nodo. Inizia con (0, 1), la radice a profondità 1. Ogni nodo viene inserito una volta, portando con sé la lunghezza del percorso che lo raggiunge, quindi la profondità massima che estrai è la risposta. Nel primo esempio, il 6 viene inserito come (9, 4).

Lo stack contiene circa un fratello in attesa per livello, O(h), senza stack delle chiamate che possa andare in overflow. Lo stesso codice funziona su un albero basato su puntatori di qualsiasi profondità.

Algoritmo

Inserisci (0, 1) in uno stack e imposta best = 0.
Estrai una coppia (i, depth) e imposta best al maggiore tra best e depth.
Per ciascun indice figlio 2*i+1 e 2*i+2 che si trova all'interno dell'array e non è -1, inseriscilo con depth + 1.
Ripeti finché lo stack non è vuoto, poi restituisci best.

def maxDepth(tree):
    n = len(tree)
    best = 0
    stack = [(0, 1)]  # (node index, depth of that node); the root is never empty
    while stack:
        i, depth = stack.pop()
        best = max(best, depth)
        for child in (2 * i + 1, 2 * i + 2):
            if child < n and tree[child] != -1:
                stack.append((child, depth + 1))
    return best

Trappole e casi limite

Contare gli archi invece dei nodi. [7, -1, -1] ha profondità 1, non 0.
Saltare il controllo dei limiti. Nel primo esempio, il 6 all’indice 9 ha indici dei figli 19 e 20, oltre la fine dell’array. Controlla child < n prima di leggere tree[child].
Calcolare la profondità a partire dalla lunghezza dell’array. Le voci -1 finali raggiungono un livello senza nodi: [7, -1, -1] ha lunghezza 3 ma profondità 1.
Leggere la dimensione della coda all’interno del ciclo del batch. I figli aggiunti durante il batch la modificano, quindi salvala prima.
Confondere l’offset in Lua e R, dove gli array iniziano da 1. Mantieni gli indici dei nodi a partire da 0 per 2*i+1 e leggi tree[i + 1].

Domande frequenti3

Qual è la complessità temporale della profondità massima di un albero binario?

Ogni approccio visita ogni nodo una volta, quindi il tempo è O(n). Le versioni in profondità usano O(h) di spazio aggiuntivo per il percorso corrente, dove h è la profondità. La versione in ampiezza usa O(w) per il livello più ampio, che contiene circa la metà dei nodi in un albero completo.

Dovresti usare DFS o BFS per calcolare la profondità massima di un albero binario?

Entrambi hanno una complessità temporale di O(n). La ricerca in profondità è più breve da scrivere e usa una quantità di memoria proporzionale alla profondità, il che la rende adatta agli alberi larghi e poco profondi. La ricerca in ampiezza conta direttamente i livelli e usa una quantità di memoria proporzionale al livello più ampio, il che la rende adatta agli alberi profondi e stretti. Per trovare la profondità minima, vince la BFS perché può fermarsi alla prima foglia.

Qual è la differenza tra la profondità e l'altezza di un albero binario?

La profondità di un nodo conta i passaggi dalla radice fino a esso; l’altezza conta i passaggi da esso fino alla foglia più profonda. La profondità massima dell’albero è uguale all’altezza della radice. Questo problema conta i nodi, quindi un singolo nodo ha profondità 1; contando gli archi si ottiene un valore inferiore di uno.

def maxDepth(tree):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]

Output atteso

Maximum Depth of Binary Tree

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Ricorsione sui due sottoalberi

Ricerca in ampiezza, livello per livello

Ricerca in profondità con uno stack esplicito

Trappole e casi limite

Domande frequenti3

Problemi simili