Subtree of Another Tree

Q: Qual è la complessità temporale di Subtree of Another Tree?

Confrontare a partire da ogni nodo costa O(n·m) nel caso peggiore, dove n e m sono le dimensioni dei due alberi. Confrontare solo i nodi la cui altezza è uguale a quella di subRoot porta il costo a O(n + m) , perché ogni nodo di root viene percorso al massimo una volta.

Q: Il sottoalbero di un altro albero può essere individuato tramite il confronto di stringhe?

Sì. Scrivi ogni albero in preordine, usando # per ogni figlio vuoto e un separatore prima di ogni valore: ,2,1,#,#,3,#,# . subRoot è un sottoalbero esattamente quando la sua stringa compare all'interno della stringa di root , e KMP lo trova in O(n + m) . Senza i marcatori, forme diverse producono la stessa stringa; senza separatori, 12 contiene 2 .

FacileVisita di alberi Ricorsione

+10

Ti vengono dati due alberi binari, root e subRoot, ciascuno memorizzato in un array in ordine per livelli: 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. Un array può terminare con ulteriori voci -1.

Restituisci true se un nodo di root, con tutti i suoi discendenti, ha esattamente la stessa forma e gli stessi valori di subRoot, e false altrimenti. Anche l'intero root conta.

Funzione

isSubtree(root: integer-array, subRoot: integer-array) → boolean

rootinteger-array: l'albero da cercare, in ordine per livelli, con -1 per uno spazio vuoto
subRootinteger-array: l'albero da cercare, nello stesso formato
Restituisceboolean: true se subRoot compare in root come nodo con tutti i suoi discendenti, false altrimenti

Vincoli

1 ≤ root.length ≤ 32767 e 1 ≤ subRoot.length ≤ 32767
Ogni elemento è -1 o un valore compreso tra 0 e 10⁴.
root[0] e subRoot[0] non sono mai -1, quindi entrambi gli alberi hanno almeno un nodo.
Entrambi gli array possono terminare con voci -1 aggiuntive dopo il loro ultimo nodo.
Entrambi i figli di uno spazio vuoto sono vuoti a loro volta e ogni albero ha una profondità massima di 14.
I valori possono ripetersi.

Esempi

Input: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
Output: true
Spiegazione: Il nodo 2 all'indice 1 ha come figli 1 e 3, ed entrambi sono foglie. Questo è esattamente subRoot.

Input: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
Output: false
Spiegazione: Il 3 sotto il nodo 2 ora ha un figlio 0. Un sottoalbero include tutti i discendenti, quindi il nodo 2 comprende quattro nodi rispetto ai tre di subRoot, e nessun altro nodo contiene un 2.

Input: root = [5, 5, 7]subRoot = [5]
Output: true
Spiegazione: La radice 5 ha due figli, quindi non corrisponde al singolo nodo 5. Il 5 all’indice 1 è una foglia e corrisponde.

Per approfondire

Puoi calcolare l’impronta digitale di ogni sottoalbero a partire dal suo valore e dalle impronte digitali dei suoi figli, così che il confronto con subRoot costi O(1)? Cosa fai quando due sottoalberi diversi entrano in collisione?

Suggerimenti

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

0 di 3 aperti

Soluzione

Il problema ha due parti: decidere se due alberi sono identici e scegliere dove in root eseguire quel controllo. Solo un nodo la cui altezza è uguale all’altezza di subRoot può corrispondere, e i nodi di una stessa altezza non si sovrappongono, quindi controllare solo quelli fa sì che ogni nodo di root venga visitato al massimo una volta.

Confronta a ogni nodo

Intuizione

Una posizione i è valida quando i è all'interno dell'array e il valore in quella posizione non è -1. Due alberi sono identici quando sono entrambi vuoti, oppure quando le loro radici contengono lo stesso valore e i rispettivi sottoalberi sinistro e destro sono identici. same(i, j) percorre in parallelo root a partire da i e subRoot a partire da j. Se subRoot compare in root, la sua radice si trova su un nodo, quindi prova same(i, 0) a partire da ogni i valido.

Una corrispondenza quasi perfetta può proseguire per un massimo di m passaggi prima di fallire, per ciascuno degli n nodi: O(n·m). In questo caso, il limite di profondità la limita: un nodo viene percorso solo dai controlli che iniziano da esso o da un nodo sopra di esso, al massimo 14 volte.

Algoritmo

Scrivi same(i, j). Se la posizione i in root e la posizione j in subRoot sono entrambe vuote, restituisci true; se lo è esattamente una, restituisci false.
Se i due valori differiscono, restituisci false. Altrimenti restituisci same(2*i+1, 2*j+1) e same(2*i+2, 2*j+2).
Restituisci true se same(i, 0) è vero per qualche indice reale i di root, e false altrimenti.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    # Try every real node of root as the top of a match.
    for i in range(n):
        if root[i] != -1 and same(i, 0):
            return True
    return False

Confronta solo quando le altezze corrispondono

Intuizione

Gli alberi identici hanno la stessa altezza, calcolata contando i nodi sul percorso più lungo verso il basso. Quindi vale la pena controllare solo i nodi di root la cui altezza è uguale a quella di subRoot. Nel primo esempio subRoot ha altezza 2, e in root lo stesso vale solo per 2 e 8.

Un nodo è più alto di tutti i nodi sottostanti, quindi due nodi della stessa altezza non si trovano mai uno dentro l’altro. Ogni controllo visita solo il sottoalbero del nodo da cui parte, quindi nel complesso i controlli visitano ogni nodo di root al massimo una volta.

I figli si trovano a indici maggiori rispetto al genitore, quindi una scansione dall’ultimo indice verso il primo raggiunge entrambi i figli prima del genitore. Le due scansioni delle altezze e i controlli richiedono un tempo O(n + m).

Algoritmo

Riempi un array delle altezze per ciascun albero, procedendo dall’ultimo indice fino a 0: una posizione vuota riceve 0, un nodo reale riceve 1 più l’altezza maggiore dei suoi due figli.
Per ogni indice i di root la cui altezza è uguale all’altezza all’indice 0 di subRoot, esegui same(i, 0) e restituisci true se è verificata.
Restituisci false.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    def heights(tree):
        # Children sit at larger indexes, so a backward scan finishes them first.
        h = [0] * len(tree)
        for i in range(len(tree) - 1, -1, -1):
            if tree[i] != -1:
                left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
                right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
                h[i] = 1 + max(left, right)
        return h

    target = heights(subRoot)[0]
    rootHeights = heights(root)
    # Only a node of the same height can match, and no two such nodes overlap.
    for i in range(n):
        if rootHeights[i] == target and same(i, 0):
            return True
    return False

Trappole e casi limite

Accettare una corrispondenza parziale, come nel secondo esempio. same deve fallire quando root ha un nodo nel punto in cui subRoot ha uno spazio vuoto.
Fermarsi al primo nodo con il valore corretto. Nel terzo esempio la radice 5 non corrisponde, mentre la foglia 5 sotto di essa corrisponde.
Confrontare porzioni dei due array. I nodi di un sottoalbero sono distribuiti su molti livelli e ciascun array può terminare con ulteriori voci -1. Un indice oltre la fine corrisponde a uno spazio vuoto, come -1.
In Lua e R, mantenere gli indici dei nodi a base 0 per il calcolo 2*i+1 e leggere root[i + 1].

Domande frequenti3

Qual è la complessità temporale di Subtree of Another Tree?

Confrontare a partire da ogni nodo costa O(n·m) nel caso peggiore, dove n e m sono le dimensioni dei due alberi. Confrontare solo i nodi la cui altezza è uguale a quella di subRoot porta il costo a O(n + m), perché ogni nodo di root viene percorso al massimo una volta.

Il sottoalbero di un altro albero può essere individuato tramite il confronto di stringhe?

Sì. Scrivi ogni albero in preordine, usando # per ogni figlio vuoto e un separatore prima di ogni valore: ,2,1,#,#,3,#,#. subRoot è un sottoalbero esattamente quando la sua stringa compare all'interno della stringa di root, e KMP lo trova in O(n + m). Senza i marcatori, forme diverse producono la stessa stringa; senza separatori, 12 contiene 2.

Un nodo che corrisponde a subRoot ma ha figli aggiuntivi conta?

No. Un sottoalbero è un nodo insieme a tutti i suoi discendenti, quindi anche ogni nodo sotto la corrispondenza deve comparire in subRoot. Nel secondo esempio, lo 0 in più sotto il 3 rende la risposta false.

def isSubtree(root, subRoot):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

root = [6, 2, 8, 1, 3, -1, 9]
subRoot = [2, 1, 3]

Output atteso

true