¿Por qué es útil el recorrido inorder y preorder para crear un algoritmo para decidir si T2 es un subárbol de T1?
Estoy mirando un libro de entrevistas y la pregunta es:
Tienes dos árboles binarios muy grandes:T1
, con millones de nodos, yT2
, con cientos de nodos. Crea un algoritmo para decidir siT2
es un subárbol deT1
.
Los autores mencionan esto como una posible solución:
Tenga en cuenta que el problema aquí especifica queT1
tiene millones de nodos, lo que significa que debemos tener cuidado con la cantidad de espacio que utilizamos. Digamos, por ejemplo,T1
tiene 10 millones de nodos, lo que significa que solo los datos son aproximadamente40 mb
. Podríamos crear una cadena que represente los recorridos inorder y preorder. SiT2
El recorrido de la preorden es una subcadena deT1
El recorrido de la preorden, yT2
El recorrido inorder es una subcadena deT1
Es transversal de orden, entoncesT2
es una subcadena deT1
.
No estoy muy seguro de la lógica detrás de por qué si estos son verdaderos:
T2-preorder-traversal-string
es una subcadena deT1-preorder-traversal-string
T2-inorder-traversal-string
es una subcadena deT1-inorder-traversal-string
EseT2
debe ser una subcadena (aunque supongo que el autor significa subárbol) deT1
. ¿Puedo obtener una explicación a esta lógica?
EDITAR: UsuarioBartoszMarcinkowski trae un buen punto Supongamos que ambos árboles no tienen nodos duplicados.