Lowest Common Ancestor of a Binary Tree

Q: In che modo è diverso dal minimo antenato comune in un albero binario di ricerca?

In un albero di ricerca, confrontare p e q con un nodo ti dice da quale lato si trova ciascuno, quindi un percorso dalla radice trova la risposta in O(h). Qui un confronto non dice nulla, quindi cerchi nei sottoalberi.

Q: Riesci a trovare l’antenato comune più basso usando i puntatori ai genitori?

Sì. In questo array, il genitore dell’indice i è (i-1)/2 arrotondato per difetto. Sposta l’indice più grande verso il suo genitore finché i due indici non sono uguali; un indice più grande non è mai un antenato di uno più piccolo. Con nodi collegati, inserisci gli antenati di p in un insieme e risali da q fino al primo che vi trovi.

MedioVisita di alberi Ricorsione

+10

Hai un albero binario nell’array root, disposto secondo l’ordine heap: la radice all’indice 0, i figli dell’indice i agli indici 2*i+1 (sinistro) e 2*i+2 (destro), e -1 per una posizione vuota. I valori sono distinti e non seguono alcun ordine.

Restituisci il valore dell’antenato comune più basso di p e q, i valori di due nodi diversi: il nodo più profondo il cui sottoalbero contiene entrambi. Un sottoalbero include il suo nodo radice, quindi se q si trova sotto p, la risposta è p.

Funzione

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

rootinteger-array: l'albero binario in ordine per livelli, con -1 per una posizione vuota
pinteger: il valore di un nodo
qinteger: il valore di un altro nodo
Restituisceinteger: il valore del nodo più basso il cui sottoalbero contiene sia p che q

Vincoli

2 ≤ root.length ≤ 32767
Ogni root[i] è -1 oppure un valore tale che 0 ≤ root[i] ≤ 10⁴.
root[0] non è mai -1 e l'albero ha almeno due nodi.
L'array può terminare con voci -1 aggiuntive oltre l'ultimo nodo.
Entrambi i figli di uno spazio vuoto sono anch’essi vuoti e la profondità è al massimo 14.
Tutti i valori nell’albero sono distinti e non sono ordinati.
p e q sono i valori di due nodi diversi dell’albero, in qualsiasi ordine.

Esempi

Input: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
Output: 3
Spiegazione: 6 è il figlio sinistro di 3, e 9 si trova sotto 4, a destra di 3, quindi si incontrano in 3. Confrontando i valori si arriverebbe alla radice 8: 6 è più piccolo e 9 più grande.

Input: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
Output: 4
Spiegazione: 7 è il figlio sinistro di 4 e il sottoalbero di 4 include 4 stesso, quindi la risposta è 4.

Input: root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
Output: 6
Spiegazione: La radice 1 non ha un figlio sinistro. Il suo figlio destro 6 ha 3 a sinistra e 0 a destra, quindi i valori si incontrano in 6.

Per approfondire

Se p o q potrebbero essere assenti, con -1 come risposta, quale scorciatoia si interrompe nel singolo passaggio e come puoi comunque completare in un'unica traversata?

Suggerimenti

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

0 di 3 aperti

Soluzione

Nessun ordine ti dice quale lato contiene un valore, quindi devi guardare. Una visita postordine consente a ogni sottoalbero di riferire ciò che ha trovato, e i valori si incontrano nel primo nodo che riceve informazioni da entrambi i lati.

Cammina verso il basso, cercando su entrambi i lati

Intuizione

Scendi dalla radice e, a ogni nodo, cerca p e q nel sottoalbero sinistro. Se ci sono entrambi: vai a sinistra. Se non c’è nessuno dei due: vai a destra. Se ce n’è uno per parte: i valori si separano e questo nodo è la risposta. Anche un nodo che contiene p o q è la risposta, perché l’altro valore deve trovarsi sotto di esso. Per 6 e 9, la radice li trova entrambi a sinistra e, in 3, il solo 6 contiene solo p.

Ogni passo verso il basso cerca in un intero sottoalbero, quindi h livelli costano O(n·h), e O(n²) in un albero alto e stretto senza limiti di profondità. La ricerca in 8 aveva già visitato ogni nodo sotto 3 e il passaggio in 3 ne visita di nuovo alcuni.

Algoritmo

Scrivi contains(i, value): false per una posizione vuota (oltre la fine o -1), true se root[i] è uguale a value, altrimenti interroga entrambi i figli.
Inizia da i = 0. Se root[i] è p o q, restituiscilo.
Se il sottoalbero sinistro in 2*i+1 contiene entrambi i valori, spostati lì. Se non ne contiene nessuno, spostati in 2*i+2.
Altrimenti restituisci root[i].

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

    def contains(i, value):
        # Is value somewhere in the subtree at index i?
        if i >= n or root[i] == -1:
            return False
        if root[i] == value:
            return True
        return contains(2 * i + 1, value) or contains(2 * i + 2, value)

    i = 0  # p and q are always inside the subtree at i
    while True:
        if root[i] == p or root[i] == q:
            return root[i]  # one value is here, the other is below it
        left = 2 * i + 1
        p_left = contains(left, p)
        q_left = contains(left, q)
        if p_left and q_left:
            i = left  # both on the left
        elif not p_left and not q_left:
            i = 2 * i + 2  # both on the right
        else:
            return root[i]  # one on each side

Un'unica visita in postordine

Intuizione

Fai in modo che ogni sottoalbero risponda una volta, dal basso verso l’alto. find(i) restituisce l’indice della risposta se il sottoalbero in i contiene entrambi i valori, l’indice di p o q se ne contiene uno e -1 se non ne contiene nessuno.

Un nodo che contiene p o q restituisce il proprio indice senza guardare sotto. Se l’altro valore si trova nel suo sottoalbero, questo nodo è la risposta; altrimenti, un nodo più in alto riceve informazioni da entrambi i lati. Qualsiasi altro nodo interroga entrambi i figli. Due risultati significano che i valori sono arrivati da lati diversi e si incontrano qui. Un singolo risultato risale invariato, che rappresenti un valore o la risposta definitiva.

Nel primo esempio, 3 riceve l’indice 3 dal figlio sinistro e 10 da quello destro, restituisce il proprio indice 1 e la radice lo propaga verso l’alto. Ogni nodo viene visitato una volta: tempo O(n), ricorsione O(h).

Algoritmo

find(i) restituisce -1 per un indice oltre la fine o un -1.
Un nodo il cui valore è p o q restituisce i senza cercare più in basso.
Qualsiasi altro nodo calcola left = find(2*i+1) e right = find(2*i+2). Se nessuno dei due è -1, restituisce i; altrimenti quello che non è -1, oppure -1.
Restituisci root[find(0)].

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

    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 root[i] == -1:
            return -1
        if root[i] == p or root[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 root[find(0)]

Trappole e casi limite

Confrontare i valori con il nodo. L'albero non ha un ordine: nel primo esempio, la ricerca si ferma alla radice 8 invece che a 3.
Restituire true o false invece di un indice. Il nodo padre non può capire se la risposta trovata si trova già sotto di esso.
Leggere un nodo figlio senza controllare la lunghezza. Il 9 all'indice 10 ha gli indici dei nodi figli 21 e 22, oltre l'ultima voce.
Restituire find(0), un indice, invece di root[find(0)].
In Lua e R, gli array iniziano da 1: mantieni gli indici dei nodi a base 0 e leggi root[i + 1].

Domande frequenti3

Qual è la complessità temporale dell'antenato comune più basso di un albero binario?

La visita post-ordine entra in ogni nodo al massimo una volta: tempo O(n). Lo stack di ricorsione contiene un frame per livello, quindi lo spazio è O(log n) in un albero bilanciato e O(n) in un albero a forma di percorso.

In che modo è diverso dal minimo antenato comune in un albero binario di ricerca?

In un albero di ricerca, confrontare p e q con un nodo ti dice da quale lato si trova ciascuno, quindi un percorso dalla radice trova la risposta in O(h). Qui un confronto non dice nulla, quindi cerchi nei sottoalberi.

Riesci a trovare l’antenato comune più basso usando i puntatori ai genitori?

Sì. In questo array, il genitore dell’indice i è (i-1)/2 arrotondato per difetto. Sposta l’indice più grande verso il suo genitore finché i due indici non sono uguali; un indice più grande non è mai un antenato di uno più piccolo. Con nodi collegati, inserisci gli antenati di p in un insieme e risali da q fino al primo che vi trovi.

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

Test #1

Test #2

Test #3

Argomenti

root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]
p = 6
q = 9

Output atteso