Lowest Common Ancestor of a BST

Q: Qual è la complessità temporale del più basso antenato comune in un BST?

La visita dalla radice segue un solo percorso, quindi richiede un tempo O(h) per un albero di profondità h e uno spazio aggiuntivo O(1). In un albero bilanciato, è O(log n); in un albero con la forma di un unico percorso, è O(n).

Q: In che modo l’LCA in un albero di ricerca binaria è diverso dall’LCA in un albero binario?

In un normale albero binario un valore può trovarsi ovunque, quindi potresti dover cercare in ogni nodo, con un lavoro O(n). In un albero di ricerca, confrontare i due valori con un nodo ti dice da che parte si trova ciascuno, quindi segui un unico percorso dalla radice.

Q: Un nodo può essere il proprio antenato comune più basso?

Sì. Un nodo conta come antenato di sé stesso, quindi quando p si trova sopra q la risposta è p , e quando i due valori sono uguali la risposta è quel valore.

MedioAlbero binario di ricerca

+10

Hai un albero di ricerca binario memorizzato nell’array tree in ordine heap: la radice si trova all’indice 0, i figli dell’indice i si trovano rispettivamente a 2*i+1 (sinistra) e 2*i+2 (destra), e -1 indica una posizione vuota. Ogni valore nel sottoalbero sinistro di un nodo è minore del valore del nodo, mentre ogni valore nel sottoalbero destro è maggiore.

Scrivi lowestCommonAncestor, che restituisce il valore dell’antenato comune più basso dei valori p e q, entrambi presenti nell’albero: il nodo più profondo che li ha entrambi nel proprio sottoalbero. Un nodo fa parte del proprio sottoalbero, quindi se p si trova sopra q, la risposta è p.

Funzione

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

treeinteger-array: l'albero binario di ricerca in ordine per livelli, con -1 per una posizione vuota
pinteger: il primo valore da trovare
qinteger: il secondo valore da trovare
Restituisceinteger: il valore del nodo più profondo che ha sia p sia q nel proprio sottoalbero

Vincoli

1 ≤ tree.length ≤ 32767
Ogni tree[i] è -1 oppure un valore tale che 0 ≤ tree[i] ≤ 10⁵.
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 una posizione vuota sono vuoti a loro volta, e la profondità è al massimo 14.
L'albero è un albero binario di ricerca valido, quindi tutti i suoi valori sono distinti.
p e q sono valori dei nodi dell’albero. Possono essere in qualsiasi ordine e possono essere uguali.

Esempi

Input: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
Output: 8
Spiegazione: Salendo da 3 e da 15, il primo nodo che raggiungono entrambi è 8: 3 è il suo figlio sinistro e 15 si trova sotto 12 sul suo lato destro. Anche la radice 20 è un antenato comune, ma più in alto.

Input: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Output: 12
Spiegazione: 10 è il figlio sinistro di 12 e un nodo è considerato antenato di sé stesso, quindi 12 contiene entrambi i valori e nessun nodo al di sotto di esso li contiene. Qui p è il valore maggiore.

Input: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Output: 70
Spiegazione: Entrambi i valori sono maggiori della radice 50, quindi si trovano entrambi alla sua destra. In corrispondenza di 70 si separano: 55 è minore e si trova a sinistra, sotto 60, mentre 80 è maggiore.

Per approfondire

Che cosa cambieresti se p o q potessero mancare dall'albero e la funzione dovesse restituire -1 in quel caso?

Suggerimenti

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

0 di 3 aperti

Soluzione

Un albero di ricerca ti indica, a ogni nodo, dove si trova un valore: i valori più piccoli a sinistra, quelli più grandi a destra. Parti dalla radice e procedi verso il lato che contiene entrambi i valori. Il primo nodo in cui smettono di condividere lo stesso lato è la risposta, e lo raggiungi seguendo un unico percorso.

Cerca nell'intero albero, ignorando l'ordine

Intuizione

Questo metodo funziona su qualsiasi albero binario. Una chiamata ricorsiva a find(i) riporta cosa contiene il sottoalbero in corrispondenza di i. Un nodo che contiene p o q riporta sé stesso: se l’altro valore si trova sotto di esso, è la risposta; altrimenti, un nodo più in alto vede entrambi. Ogni altro nodo interroga entrambi i figli. Se entrambi riportano qualcosa, p e q si trovano su lati diversi e questo nodo è il punto in cui si incontrano; se lo riporta uno solo, risali quel risultato.

Per 3 e 15, 8 riceve l’indice 3 da sinistra e l’indice 10 da destra e riporta sé stesso. Potrebbe visitare ogni nodo: tempo O(n) e O(h) per la ricorsione.

Algoritmo

Scrivi find(i). Se la posizione in i è vuota (oltre la fine o -1), restituisci -1.
Se tree[i] è p o q, restituisci i.
Chiama find su 2*i+1 e 2*i+2. Se entrambe hanno trovato qualcosa, restituisci i.
Altrimenti restituisci il lato che ha trovato qualcosa, oppure -1.
Restituisci tree[find(0)].

def lowestCommonAncestor(tree, p, q):
    n = len(tree)

    def find(i):
        # In the subtree at index i: the index of the answer if both values are
        # inside, the index of the one that is, or -1 when neither is.
        if i >= n or tree[i] == -1:
            return -1
        if tree[i] == p or tree[i] == q:
            return i
        left = find(2 * i + 1)
        right = find(2 * i + 2)
        if left != -1 and right != -1:
            return i  # one value on each side: this node is the answer
        return left if left != -1 else right

    return tree[find(0)]

Confronta i due percorsi di ricerca

Intuizione

Cerca un valore nel modo consueto: parti dalla radice, vai a sinistra se è minore del nodo e a destra se è maggiore. Il percorso dalla radice a un nodo è unico, quindi la visita attraversa tutti gli antenati del valore e nient’altro.

Registra entrambi i percorsi. Condividono i nodi finché i valori non prendono direzioni diverse, quindi l’inizio condiviso elenca gli antenati comuni e il suo ultimo valore è il più basso. Per 3 e 15, i percorsi sono 20, 8, 3 e 20, 8, 12, 15: condividono 20, 8, quindi la risposta è 8. Ogni visita richiede un passo per livello: tempo O(h) e spazio O(h) per gli elenchi.

Algoritmo

Scrivi path(target): inizia dall'indice 0, registra tree[i], fermati quando è uguale a target, altrimenti spostati a 2*i+1 se target è minore e a 2*i+2 se è maggiore.
Costruisci il percorso fino a p e il percorso fino a q.
Scorri entrambe le liste dall'inizio e restituisci l'ultimo valore che condividono.

def lowestCommonAncestor(tree, p, q):
    def path(target):
        # The values met on the way from the root down to target.
        values = []
        i = 0
        while True:
            values.append(tree[i])
            if tree[i] == target:
                return values
            i = 2 * i + 1 if target < tree[i] else 2 * i + 2

    to_p, to_q = path(p), path(q)
    # Both paths start at the root; the answer is the last value they share.
    answer = to_p[0]
    for a, b in zip(to_p, to_q):
        if a != b:
            break
        answer = a
    return answer

Scendi finché i valori non si separano

Intuizione

I due percorsi coincidono finché p e q procedono nella stessa direzione, quindi percorriamoli entrambi contemporaneamente. In un nodo che contiene v, se entrambi i valori sono minori, entrambi si trovano nel sottoalbero sinistro, così come ogni antenato comune al di sotto di v: vai a sinistra. Se entrambi sono maggiori, vai a destra.

Altrimenti un valore è minore e l’altro maggiore, quindi nessun figlio di v contiene entrambi, oppure uno dei due è uguale a v, che è antenato di sé stesso. In entrambi i casi v è il nodo più profondo che si trova sopra entrambi. Nel terzo esempio, 50 è minore di entrambi i valori, quindi vai a destra fino a 70, dove 55 è minore e 80 maggiore. Una coppia di confronti per livello dà un tempo O(h) e uno spazio O(1).

Algoritmo

Inizia dall’indice i = 0.
Leggi v = tree[i].
Se p < v e q < v, spostati a 2*i+1 e ripeti.
Se p > v e q > v, spostati a 2*i+2 e ripeti.
Altrimenti restituisci v.

def lowestCommonAncestor(tree, p, q):
    i = 0  # start at the root
    while True:
        value = tree[i]
        if p < value and q < value:
            i = 2 * i + 1  # both are smaller: the answer is on the left
        elif p > value and q > value:
            i = 2 * i + 2  # both are larger: the answer is on the right
        else:
            return value  # they split here, or one of them is this node

Trappole e casi limite

Usare ≤ e ≥ nei test di spostamento. Con p = 12 e q = 10, il percorso supera 12 e arriva a 10, poi restituisce 10 oppure esce dall’albero.
Supporre che p < q. Nel secondo esempio, p è il valore maggiore. Verifica entrambi rispetto al nodo oppure scambiali prima.
Restituire l’indice invece del valore. La risposta è tree[i], non i.
In Lua e R, gli array iniziano da 1. Mantieni gli indici dei nodi a partire da 0 per l’aritmetica 2*i+1 e leggi tree[i + 1].

Domande frequenti3

Qual è la complessità temporale del più basso antenato comune in un BST?

La visita dalla radice segue un solo percorso, quindi richiede un tempo O(h) per un albero di profondità h e uno spazio aggiuntivo O(1). In un albero bilanciato, è O(log n); in un albero con la forma di un unico percorso, è O(n).

In che modo l’LCA in un albero di ricerca binaria è diverso dall’LCA in un albero binario?

In un normale albero binario un valore può trovarsi ovunque, quindi potresti dover cercare in ogni nodo, con un lavoro O(n). In un albero di ricerca, confrontare i due valori con un nodo ti dice da che parte si trova ciascuno, quindi segui un unico percorso dalla radice.

Un nodo può essere il proprio antenato comune più basso?

Sì. Un nodo conta come antenato di sé stesso, quindi quando p si trova sopra q la risposta è p, e quando i due valori sono uguali la risposta è quel valore.

def lowestCommonAncestor(tree, p, q):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

Output atteso

Lowest Common Ancestor of a BST

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Cerca nell'intero albero, ignorando l'ordine

Confronta i due percorsi di ricerca

Scendi finché i valori non si separano

Trappole e casi limite

Domande frequenti3

Problemi simili