Construct Binary Tree from Preorder and Inorder Traversal

Q: ¿Puedes reconstruir un árbol binario a partir de los recorridos en preorden y postorden?

No en general. El recorrido en preorden [1, 2] y el recorrido en postorden [2, 1] son compatibles tanto con un hijo izquierdo como con uno derecho, porque ninguno de los recorridos coloca la raíz entre sus subárboles. El par solo es suficiente para un árbol binario lleno, donde cada nodo tiene cero o dos hijos.

MedioRecorrido de árboles Hashing Recursión

+10

Recibes dos arreglos, preorder e inorder, que contienen los valores distintos del mismo árbol binario. El recorrido en preorden visita un nodo, después su subárbol izquierdo y luego su subárbol derecho. El recorrido en inorden visita el subárbol izquierdo, después el nodo y luego el subárbol derecho.

Reconstruye el árbol y devuélvelo como un arreglo en orden por niveles: la raíz en el índice 0, los hijos del índice i en 2i+1 (izquierdo) y 2i+2 (derecho), y -1 para cada espacio vacío. El arreglo termina en el último nodo, sin ningún -1 final.

Función

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: los valores en preorden: nodo, subárbol izquierdo, subárbol derecho
inorderinteger-array: los valores en orden: subárbol izquierdo, nodo, subárbol derecho
Devuelveinteger-array: el árbol en orden por niveles, con -1 para las posiciones vacías y sin -1 al final

Restricciones

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴, y todos los valores son distintos.
inorder contiene los mismos valores, y ambos arreglos describen el mismo árbol binario.
La profundidad del árbol es como máximo 14, así que todos los índices de la respuesta son menores que 2¹⁴-1 = 16383.

Ejemplos

Entrada: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Salida: [7, 3, 4, 0, 9, -1, 6]
Explicación: El recorrido en preorden empieza con la raíz, 7. Está en la posición 3 del recorrido inorder, así que 0, 3, 9 van a la izquierda y 4, 6 van a la derecha. 4 solo tiene un hijo derecho, 6, así que el índice 5 sigue siendo -1.

Entrada: preorder = [1, 2, 3]inorder = [2, 3, 1]
Salida: [1, 2, -1, -1, 3]
Explicación: La raíz 1 aparece al final de inorder, así que el índice 2 es -1. De 2, 3, preorder enumera primero 2 e inorder coloca 3 después, así que 3 es su hijo derecho, en el índice 4.

Para ir más allá

¿Puedes reconstruir el árbol sin recursión, en una sola pasada sobre preorder con una pila explícita?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

El recorrido en preorden da la raíz de cada subárbol: el primer valor de su tramo. El recorrido en inorden da la división: los valores anteriores a la raíz van a la izquierda y los posteriores, a la derecha. La recursión en ambas mitades reconstruye el árbol, y un mapa de valores a posiciones en el recorrido en inorden permite encontrar cada raíz en un solo paso.

Divide recursivamente, buscando la raíz

Intuición

En el recorrido preorden, el subárbol izquierdo va después de su raíz y ocupa una entrada por valor, m-lo en total, donde m es la posición de la raíz en el recorrido inorden. El subárbol derecho va después, así que su raíz se encuentra en pre+1+(m-lo). En el primer ejemplo, la parte izquierda 0, 3, 9 tiene tres valores, así que el subárbol derecho comienza en el índice de preorden 4, el valor 4.

Una profundidad de como máximo 14 mantiene todos los índices de salida por debajo de 2^14-1. Rellena esa cantidad de celdas con -1, escribe cada valor en su índice y elimina las entradas -1 finales.

Buscar la raíz en cada rango inorden cuesta O(n·h): los rangos de un mismo nivel no se superponen, así que cada nivel recorre como máximo n entradas, es decir, como máximo 14 × 3000 = 42000 pasos en este caso. Sin límite de profundidad, un árbol con forma de camino hace que el costo sea O(n²).

Algoritmo

Crea out con 2^14-1 entradas, todas -1.
Escribe build(pre, lo, hi, h): if lo > hi, return. De lo contrario, escribe preorder[pre] en out[h].
Recorre inorder desde lo para encontrar la posición m de la raíz. El subárbol izquierdo tiene m-lo valores.
Llama a build(pre+1, lo, m-1, 2*h+1) y a build(pre+1+(m-lo), m+1, hi, 2*h+2).
Llama a build(0, 0, n-1, 0), después elimina las entradas -1 finales y devuelve el resto.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Divide recursivamente con un mapa de posiciones

Intuición

Los valores son distintos, así que cada uno tiene exactamente una posición en inorder. Regístrala en un mapa de valores a posiciones antes de que empiece la recursión, y cada búsqueda de raíz se hará en un solo paso.

Construir el mapa toma O(n), y luego cada valor se coloca una vez con trabajo constante, así que el tiempo total es O(n). El mapa ocupa O(n) espacio y la recursión, un marco por nivel. En C y R, los valores son como máximo 10^4, así que un arreglo simple de 10^4+1 entradas sirve como mapa.

Algoritmo

Construye un mapa de cada valor de inorder a su posición.
Crea out con 2^14-1 entradas, todas -1.
En build(pre, lo, hi, h), retorna si lo > hi; de lo contrario, escribe preorder[pre] en out[h] y busca su posición m en el mapa.
Haz recursión con build(pre+1, lo, m-1, 2*h+1) y build(pre+1+(m-lo), m+1, hi, 2*h+2).
Llama a build(0, 0, n-1, 0), después elimina las entradas -1 finales y devuelve el resto.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Errores comunes y casos límite

Empezar el subárbol derecho en pre+1+m en lugar de pre+1+(m-lo). Funciona mientras lo sea 0, como en la llamada inicial, y falla cuando un rango empieza más adelante.
Omitir los espacios vacíos. Un hijo ausente sigue ocupando su posición, así que el segundo ejemplo devuelve [1, 2, -1, -1, 3], no [1, 2, 3].
Dejar entradas -1 finales. Devolver las 2^14-1 celdas da al primer ejemplo 16376 entradas -1 adicionales.
Copiar segmentos de ambos arreglos en cada llamada, lo que añade O(n) por nivel. Pasa rangos de índices.
En Lua y R, los arreglos empiezan en 1. Mantén las posiciones basadas en 0 para los cálculos y lee preorder[pre + 1] y out[h + 1].

Preguntas frecuentes3

¿Por qué necesitas tanto el recorrido en preorden como el recorrido en inorden para reconstruir un árbol binario?

El recorrido en preorden por sí solo no determina la forma. El recorrido en preorden [1, 2] es compatible con un árbol en el que 2 es el hijo izquierdo de 1 y con otro en el que es el hijo derecho. El recorrido en inorden lo resuelve: [2, 1] sitúa 2 a la izquierda, y [1, 2], a la derecha. Con valores distintos, el par describe exactamente un árbol.

¿Cuál es la complejidad temporal de construir un árbol binario a partir de los recorridos en preorden e inorden?

Con un mapa de valores a posiciones en el recorrido inorden, el tiempo es O(n) y el espacio adicional es O(n). Sin el mapa, buscar la raíz en cada intervalo inorden cuesta O(n·h), lo que se convierte en O(n²) en un árbol con forma de camino.

¿Puedes reconstruir un árbol binario a partir de los recorridos en preorden y postorden?

No en general. El recorrido en preorden [1, 2] y el recorrido en postorden [2, 1] son compatibles tanto con un hijo izquierdo como con uno derecho, porque ninguno de los recorridos coloca la raíz entre sus subárboles. El par solo es suficiente para un árbol binario lleno, donde cada nodo tiene cero o dos hijos.

def buildTree(preorder, inorder):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumentos

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

Salida Esperada

[7, 3, 4, 0, 9, -1, 6]