Lowest Common Ancestor of a BST

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

La discesa dalla radice segue un unico percorso, quindi richiede un tempo di O(h) per un albero di profondità h e uno spazio aggiuntivo di O(1) . In un albero bilanciato è O(log n) ; in un albero a forma di percorso singolo è 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 cerchi in entrambi i sottoalberi di ogni nodo e il lavoro è O(n) . In un albero di ricerca, confrontare i due valori con un nodo ti dice da quale parte si trova ciascuno dei due, quindi segui un solo percorso dalla radice. Il metodo ricorsivo per alberi qualsiasi funziona anche su un albero di ricerca, ma ignora queste informazioni.

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

Sì. Un nodo è considerato un antenato di sé stesso, quindi quando p si trova sopra q , la risposta è p . La stessa regola restituisce p quando i due valori sono uguali. La visita gestisce entrambi i casi: si ferma non appena il nodo corrente è uguale a uno dei valori.

Q: Perché il percorso si ferma al primo nodo in cui p e q si separano?

A quel nodo un valore è minore e l’altro maggiore, quindi si trovano in sottoalberi diversi. Qualsiasi nodo al di sotto si trova in uno solo di questi sottoalberi e non può contenere entrambi. Il nodo di separazione contiene entrambi e nessun nodo più in profondità lo fa: questa è esattamente la definizione dell’antenato comune più basso.

MedioAlbero binario di ricerca

+10

Ti viene dato un albero di ricerca binario memorizzato nell’array tree in ordine per livelli e due valori p e q che compaiono entrambi al suo interno. 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 altre voci -1. In un albero di ricerca binario, ogni valore nel sottoalbero sinistro di un nodo è minore del valore del nodo, mentre ogni valore nel suo sottoalbero destro è maggiore.

Scrivi una funzione chiamata lowestCommonAncestor che restituisca il valore del più basso antenato comune di p e q: il nodo più profondo che li ha entrambi nel proprio sottoalbero. Un nodo è considerato parte del proprio sottoalbero, quindi se p si trova sopra q, la risposta è p stesso.

Funzione

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

treeinteger-array: l'albero binario di ricerca in ordine di livello, 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 con 0 ≤ tree[i] ≤ 10⁵.
tree[0] non è mai -1, quindi l’albero ha almeno un nodo.
L'array può terminare con ulteriori voci -1 dopo l'ultimo nodo.
Entrambi i figli di uno spazio vuoto sono vuoti, e la profondità è al massimo 14.
L'albero è un albero di ricerca binario 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: Il 3 è il figlio sinistro di 8, e il 15 si trova sotto 12, a destra di 8. Risalendo da ciascuno di essi, il primo nodo che entrambi raggiungono è 8, quindi questa è la risposta; anche la radice 20 è un antenato comune, ma si trova più in alto.

Input: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Output: 12
Spiegazione: Il 10 è il figlio sinistro di 12. Un nodo è considerato antenato di sé stesso, quindi 12 contiene entrambi i valori nel suo sottoalbero e nessun nodo al di sotto di esso li contiene: la risposta è 12. I valori possono essere in qualsiasi ordine; qui p è quello più grande.

Input: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Output: 70
Spiegazione: Sia 55 che 80 sono maggiori della radice 50, quindi si trovano entrambi alla sua destra. In corrispondenza di 70 prendono strade diverse: 55 è minore e si trova a sinistra (sotto 60), 80 è maggiore e si trova a destra. Quindi 70 è la risposta.

+12 test nascosti all’invio

Per approfondire

Che cosa cambieresti se p o q potessero non essere presenti nell’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

In un normale albero binario non puoi sapere dove si trova un valore senza cercare su entrambi i lati di ogni nodo. Un albero di ricerca ti indica, a ogni nodo, che i valori più piccoli si trovano a sinistra e quelli più grandi a destra. Quindi parti dalla radice e procedi verso il lato che contiene entrambi i valori. Il primo nodo in cui non si trovano più dallo stesso lato è la risposta: lo trovi seguendo un solo percorso, senza mai esaminare il resto dell’albero.

Cerca nell'intero albero, ignorando l'ordine

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 è nell’array e il valore in quella posizione non è -1. In [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15], la radice 20 ha 8 e 31 agli indici 1 e 2, e il 12 all’indice 4 ha 10 e 15 agli indici 9 e 10.

Questo primo metodo funziona con qualsiasi albero binario. Una find(i) ricorsiva indica cosa contiene il sottoalbero all’indice i. Una posizione vuota restituisce -1. Un nodo che contiene p o q restituisce sé stesso: l’altro valore si trova al di sotto e allora questo nodo è la risposta, oppure l’altro valore si trova altrove e un nodo più in alto vedrà entrambi. Altrimenti, il nodo interroga entrambi i figli. Se entrambi i lati restituiscono qualcosa, p si trova da un lato e q dall’altro, quindi questo nodo è il punto in cui si incontrano. Se solo un lato restituisce qualcosa, lo si passa al nodo superiore.

Per p = 3 e q = 15, il nodo 8 riceve l’indice 3 dal figlio sinistro e l’indice 10 dal figlio destro, quindi restituisce sé stesso. La radice riceve questo risultato dal figlio sinistro e -1 dal figlio destro, e passa il 8 al nodo superiore.

È corretto, ma potrebbe visitare ogni nodo: tempo O(n), con O(h) per la ricorsione. Non sfrutta mai l’ordinamento dei valori, che è proprio il vantaggio di un albero di ricerca.

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 entrambi hanno trovato qualcosa, restituisci i.
Altrimenti restituisci il valore del 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

Ora usa l’ordine. Puoi trovare un valore nel modo in cui si dovrebbe cercare in un albero di ricerca: parti dalla radice, vai a sinistra quando il valore è minore del nodo, a destra quando è maggiore e fermati quando lo raggiungi. Questo percorso attraversa tutti gli antenati del valore e nient’altro, perché il percorso dalla radice a un nodo è unico.

Registra il percorso per p e quello per q. Entrambi partono dalla radice e seguono gli stessi nodi finché i valori non prendono direzioni diverse. La parte iniziale condivisa è l’elenco dei loro antenati comuni, quindi l’ultimo valore condiviso è quello più in basso. Per 3 e 15 i percorsi sono 20, 8, 3 e 20, 8, 12, 15: condividono 20, 8 e la risposta è 8. Per 12 e 10 sono 20, 8, 12 e 20, 8, 12, 10, e la risposta è 12.

Ogni percorso richiede un passaggio per livello, quindi il tempo è O(h), al massimo 14 passaggi qui, indipendentemente dal numero di nodi contenuti nell’albero. I due elenchi richiedono O(h) spazio.

Algoritmo

Scrivi path(target): inizia dall’indice 0, registra tree[i], fermati quando è uguale a target, altrimenti spostati su 2*i+1 se target è minore e su 2*i+2 se è maggiore.
Costruisci il percorso fino a p e il percorso fino a q.
Percorri entrambi gli elenchi dall’inizio finché i valori corrispondono, ricordando l’ultima corrispondenza.
Restituisci quell’ultimo valore condiviso.

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 dividono

Intuizione

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

Altrimenti sei arrivato. O un valore è minore di v e l’altro è maggiore, quindi si trovano in sottoalberi diversi e nessun figlio di v li contiene entrambi; oppure uno dei due è uguale a v, e un nodo è antenato di sé stesso. In entrambi i casi, v è il nodo più profondo che si trova sopra entrambi.

Nel terzo esempio la radice 50 si trova sotto 55 e 80, quindi vai a destra fino a 70. Qui 55 è minore e 80 maggiore: la risposta è 70. Nel secondo esempio vai da 20 a 8 e poi a 12, che è uguale a p, e ti fermi.

Segui un unico percorso dalla radice, con una coppia di confronti per livello, quindi il tempo è O(h) e lo spazio è O(1). Il resto dell’albero non viene mai letto.

Algoritmo

Inizia dall'indice i = 0.
Leggi v = tree[i].
Se p < v e q < v, spostati su 2*i+1 e ripeti.
Se p > v e q > v, spostati su 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

La camminata è breve, quindi la maggior parte degli errori dipende dalla regola di arresto.

Usare ≤ e ≥ nei controlli degli spostamenti. Con p = 12 e q = 10, il controllo p ≤ 12 e q ≤ 12 supera la risposta, arrivando a 10, e da lì la camminata restituisce 10 oppure esce dall’albero. Spostati solo quando entrambi i valori si trovano strettamente dallo stesso lato.
Supporre che p < q. I valori possono presentarsi in qualsiasi ordine. Confrontali entrambi con il nodo oppure scambiali prima, così che p sia il più piccolo.
Dimenticare che un valore può essere l’antenato dell’altro. In tal caso la risposta è quel valore stesso, non il suo genitore.
Restituire l’indice invece del valore. La funzione restituisce tree[i], non i.
Esplorare l’intero albero. Si ottiene la risposta corretta, ma si visitano fino a tutti i nodi quando basta seguire un solo percorso.
Confondere l’offset in Lua e R, dove gli array iniziano da 1. Mantieni gli indici dei nodi a base 0 per il calcolo 2*i+1 e leggi tree[i + 1].

Domande frequenti4

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

La discesa dalla radice segue un unico percorso, quindi richiede un tempo di O(h) per un albero di profondità h e uno spazio aggiuntivo di O(1). In un albero bilanciato è O(log n); in un albero a forma di percorso singolo è 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 cerchi in entrambi i sottoalberi di ogni nodo e il lavoro è O(n). In un albero di ricerca, confrontare i due valori con un nodo ti dice da quale parte si trova ciascuno dei due, quindi segui un solo percorso dalla radice. Il metodo ricorsivo per alberi qualsiasi funziona anche su un albero di ricerca, ma ignora queste informazioni.

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

Sì. Un nodo è considerato un antenato di sé stesso, quindi quando p si trova sopra q, la risposta è p. La stessa regola restituisce p quando i due valori sono uguali. La visita gestisce entrambi i casi: si ferma non appena il nodo corrente è uguale a uno dei valori.

Perché il percorso si ferma al primo nodo in cui p e q si separano?

A quel nodo un valore è minore e l’altro maggiore, quindi si trovano in sottoalberi diversi. Qualsiasi nodo al di sotto si trova in uno solo di questi sottoalberi e non può contenere entrambi. Il nodo di separazione contiene entrambi e nessun nodo più in profondità lo fa: questa è esattamente la definizione dell’antenato comune più basso.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

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 dividono

Trappole e casi limite

Domande frequenti4

Problemi simili