Balanced Binary Tree

+10

L'array root contiene un albero binario. La radice si trova all'indice 0, i figli dell'indice i si trovano in 2*i+1 (sinistra) e 2*i+2 (destra), -1 indica una posizione vuota e alla fine possono esserci ulteriori voci -1.

Restituisci true se l'albero è bilanciato in altezza, ovvero se in ogni nodo le altezze dei sottoalberi sinistro e destro differiscono al massimo di 1, e false altrimenti. L'altezza di un sottoalbero è il numero di nodi sul suo percorso discendente più lungo; un sottoalbero vuoto ha altezza 0.

Funzione

isBalanced(root: integer-array) → boolean

rootinteger-array: l’albero binario in ordine per livelli, con -1 per uno spazio vuoto
Restituisceboolean: vero se le altezze dei due sottoalberi di ogni nodo differiscono al massimo di 1, falso altrimenti

Vincoli

1 ≤ root.length ≤ 32767
Ogni root[i] è -1 oppure un valore con 0 ≤ root[i] ≤ 10⁵.
root[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 una posizione vuota sono vuoti a loro volta e la profondità è al massimo 14.
I valori dei nodi sono distinti.

Esempi

Input: root = [5, 2, 9, -1, -1, 7, 11]
Output: true
Spiegazione: Il sottoalbero sinistro della radice è il singolo nodo 2, con altezza 1. Il suo sottoalbero destro 9, 7, 11 ha altezza 2. Differiscono di 1 e ogni altro nodo ha due sottoalberi della stessa altezza.

Input: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
Output: false
Spiegazione: Entrambi i lati della radice hanno altezza 3, ma il nodo 3 non soddisfa la condizione: il suo sottoalbero sinistro 1, 0 ha altezza 2 e quello destro è vuoto.

Input: root = [4, 2, -1, 1]
Output: false
Spiegazione: La radice ha la catena 2, 1 alla sua sinistra, altezza 2, e nulla alla sua destra, altezza 0. Una differenza di 2 è eccessiva.

Per approfondire

Riesci a controllare l’albero senza ricorsione, usando uno stack esplicito?

Suggerimenti

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

0 di 3 aperti

Soluzione

La regola si applica a ogni nodo, quindi un albero la cui radice sembra bilanciata può comunque non rispettarla più in basso, come accade nel secondo esempio in corrispondenza di 3. Una visita in post-ordine calcola una sola volta l’altezza di ogni sottoalbero e segnala il mancato rispetto della regola non appena si verifica, in O(n).

Ricalcola le altezze in ogni nodo

Intuizione

Trasforma la definizione in codice. height(i) è 0 in una posizione vuota e, altrove, è 1 più dell’altezza del figlio più alto. Confronta le altezze dei due figli in ogni nodo reale; il primo nodo in cui differiscono di più di 1 rende la risposta false.

Ogni controllo percorre l’intero sottoalbero sotto il suo nodo, quindi un nodo viene percorso una volta per ogni nodo che lo precede: O(n·h). Con al massimo 14 livelli, un albero completo di 16,383 nodi richiede circa 2 × 10^5 passaggi. Una catena di n nodi richiederebbe O(n²).

Algoritmo

Definisci height(i) come 0 per un indice oltre la fine o un -1, e come 1 + max(height(2*i+1), height(2*i+2)) per un nodo reale.
Visita ogni indice i che contiene un nodo reale.
Se height(2*i+1) e height(2*i+2) differiscono di più di 1, restituisci false.
Se il ciclo termina senza errori, restituisci true.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

Un'unica visita in postordine che restituisce l'altezza o segnala un errore

Intuizione

Il controllo in un nodo richiede le altezze dei suoi due sottoalberi, che sono anche ciò che il nodo deve usare per comunicare la propria altezza. Quindi ottienile entrambe con una visita in postordine: ogni chiamata restituisce l’altezza del proprio sottoalbero dopo che entrambi i figli hanno restituito la loro.

Anche un fallimento più in basso deve propagarsi verso l’alto. Un’altezza reale non è mai negativa, quindi usa -1 per indicarlo: una chiamata restituisce -1 se un figlio ha restituito -1 o se le altezze dei figli differiscono di più di 1. Nel secondo esempio il 3 vede le altezze 2 e 0 e restituisce -1; la radice lo propaga senza visitare il proprio lato destro.

Nessun nodo viene raggiunto due volte, quindi il tempo è O(n), con O(h) chiamate sullo stack.

Algoritmo

Scrivi check(i). Per un indice oltre la fine o un -1, restituisci 0.
Calcola left = check(2*i+1). Se è -1, restituisci -1.
Calcola right = check(2*i+2). Se è -1, o left e right differiscono di più di 1, restituisci -1.
Altrimenti restituisci 1 + max(left, right).
Restituisci se check(0) non è -1.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

Trappole e casi limite

Controllare solo la radice. Nel secondo esempio entrambi i lati della radice hanno altezza 3, eppure il nodo 3 differisce di 2.
Confrontare la foglia più superficiale e quella più profonda. L’albero bilanciato più piccolo di altezza 6 ha foglie alle profondità 4 e 6, e ogni nodo al suo interno supera il controllo.
Perdere un errore durante la risalita. Se un figlio restituisce -1 e il genitore calcola 1 + max(-1, 2), l’errore si trasforma di nuovo in un’altezza.
Usare la lunghezza dell’array come altezza. Le voci -1 finali rendono l’array più lungo della profondità dell’albero.
In Lua e R, gli array iniziano da 1. Mantieni gli indici dei nodi a partire da 0 per 2*i+1 e leggi root[i + 1].

Domande frequenti3

Qual è la complessità temporale di Balanced Binary Tree?

Una visita in post-ordine entra in ogni nodo una volta: tempo O(n) e spazio dello stack O(h) per un albero di altezza h. Ricalcolare le altezze in ogni nodo costa O(n·h), che diventa O(n²) in una catena.

Che cosa significa bilanciato in altezza per un albero binario?

In ogni nodo, le altezze dei sottoalberi sinistro e destro differiscono al massimo di 1. Gli alberi AVL ripristinano questa proprietà dopo ogni inserimento ed eliminazione, mantenendo la loro altezza pari a O(log n).

Un albero binario completo è sempre bilanciato?

Sì. Ogni livello di un albero completo è pieno, tranne eventualmente l’ultimo, che si riempie da sinistra, quindi in ogni nodo le altezze dei due sottoalberi differiscono al massimo di 1. Il contrario non è vero: un albero bilanciato può avere spazi vuoti a sinistra nell’ultimo livello.

def isBalanced(root):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

root = [5, 2, 9, -1, -1, 7, 11]

Output atteso

true