Algoritmo per identificare se l'albero è sottostruttura dell'altro albero

Question

Sto leggendo il cracking dell'intervista di codifica e ho una domanda sulla soluzione del seguente problema: Hai due alberi binari molto grandi: T1, con milioni di nodi, e T2, con centinaia di nodi. Creare un algoritmo per decidere se T2 è un sottoalbero di T1.

La soluzione semplice che suggerisce è di creare una stringa che rappresenta gli attraversamenti in ordine e pre-order e verificare se T2s pre-ordine/in ordine di attraversamento è sottostringa di attraversamento pre-ordine/in ordine di T1.

Quello che mi chiedo è perché dobbiamo confrontare entrambi gli attraversamenti? E perché esattamente quei due attraversamenti, perché non per esempio in ordine e dopo l'ordine. E soprattutto non basterà una sola traversata? Dì solo attraversamenti in ordine o pre-ordine?

Answer 1

Un attraversamento non è sufficiente. Considerare i grafici 1-> 2-> 3 e 2 < -1-> 3. Se si inizia con il nodo 1 e si fa un attraversamento, si incontrano i nodi nell'ordine 1, 2, 3. Se si crea semplicemente una stringa che mostra il pre-ordine, i due danno lo stesso risultato: 1,2,3

Sull'altro mano, se usi un post-ordine, i due daranno un risultato diverso. 3,2,1 e 2,3,1

Scommetto che per qualsiasi ordine, è possibile trovare due alberi diversi con lo stesso risultato.

Quindi la domanda a cui devi rispondere per ogni altra coppia che vuoi guardare è: ci sarebbe un albero che darebbe lo stesso ordine per entrambi gli attraversamenti? Ho intenzione di lasciarlo come qualcosa a cui pensare e tornare più tardi per vedere se ce l'hai.

Answer 2

Penso che il preorder traversal con sentinella per rappresentare il nodo null sia sufficiente. possiamo usare questo approccio per serializzare/deserializzare un albero binario. Ciò significa che è una mappatura uno-a-uno tra un albero binario e la sua preordinazione + rappresentazione sentinella.

Dopo aver ottenuto stringhe sia per il piccolo albero che per il grande albero. quindi eseguiamo una corrispondenza stringa utilizzando l'algoritmo kmp.

So che le persone dicono che dobbiamo utilizzare sia il preorder che l'inorder (o postorder e inorder). ma la maggior parte di loro segue solo ciò che gli altri stanno dicendo, piuttosto che pensare in modo indipendente.