Invert Binary Tree

Q: ¿Cuál es la complejidad temporal de invertir un árbol binario?

Cada nodo se visita una vez, por lo que el tiempo es O(n) . Una solución recursiva usa O(h) de espacio en la pila para un árbol de profundidad h , y una basada en colas usa O(w) para el nivel más ancho. En esta versión con arreglos, la respuesta es un arreglo nuevo, lo que añade O(n) .

FácilRecorrido de árboles

+10

Recibes un árbol binario almacenado en el arreglo tree en orden por niveles. La raíz se encuentra en el índice 0; los hijos del nodo en el índice i se encuentran en 2*i+1 (izquierda) y 2*i+2 (derecha); -1 marca una posición vacía, y el arreglo puede terminar con entradas adicionales -1.

Invierte el árbol: intercambia los hijos izquierdo y derecho de cada nodo, de modo que todo el árbol se convierta en su imagen especular. Devuelve el árbol invertido en el mismo formato, sin entradas -1 al final.

Función

invertTree(tree: integer-array) → integer-array

treeinteger-array: el árbol binario por niveles, con -1 para indicar una posición vacía
Devuelveinteger-array: el árbol reflejado en orden por niveles, sin entradas -1 al final

Restricciones

1 ≤ tree.length ≤ 16383
Cada tree[i] es -1 o un valor con 0 ≤ tree[i] ≤ 1000.
tree[0] nunca es -1, así que el árbol tiene al menos un nodo.
El arreglo puede terminar con entradas -1 adicionales después del último nodo.
Ambos hijos de un espacio vacío también están vacíos, y la profundidad es como máximo 14.

Ejemplos

Entrada: tree = [5, 3, 8, 1, 4, -1, 9]
Salida: [5, 8, 3, 9, -1, 4, 1]
Explicación: Los hijos de la raíz, 3 y 8, intercambian lugares. Debajo de ellos, el 1 y el 4 que estaban debajo de 3 vuelven como 4 y 1, y 8, que solo tenía un hijo derecho, 9, ahora lo tiene a su izquierda.

Entrada: tree = [2, 7, -1, 6]
Salida: [2, -1, 7, -1, -1, -1, 6]
Explicación: La cadena 2, 7, 6 se inclina hacia la izquierda y su reflejo hacia la derecha. El 7 pasa del índice 1 al índice 2 y el 6 del índice 3 al índice 6, así que la respuesta es más larga que la entrada, con -1 en cada espacio vacío antes del último nodo.

Entrada: tree = [1, -1, -1]
Salida: [1]
Explicación: Un único nodo es su propio reflejo. Las dos entradas -1 son relleno, y la respuesta elimina todos los -1 del final.

+14 pruebas ocultas al enviar

Para ir más allá

¿Cómo comprobarías si un árbol es su propio reflejo, usando los mismos pares de índices pero sin crear la copia invertida?

Pistas

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

0 de 3 abiertas

Solución

Reflejar un árbol significa que cada nodo intercambia sus subárboles izquierdo y derecho, hasta llegar al final. Con objetos de nodo, eso supone un intercambio por nodo. En esta representación con un arreglo, la posición de un nodo es su índice, así que intercambiar dos subárboles significa mover todos los nodos que contienen. La forma de hacerlo es construir la respuesta en un nuevo arreglo y copiar cada nodo directamente a su índice reflejado, llevando pares de índices durante un recorrido: dónde está ahora el nodo y adónde va.

Recursión que coloca cada nodo en su índice reflejado

Intuición

Primero, cómo moverse por el arreglo. El nodo en el índice i tiene su hijo izquierdo en 2*i+1 y su hijo derecho en 2*i+2. Un hijo existe solo si su índice está dentro del arreglo y el valor allí no es -1. En [5, 3, 8, 1, 4, -1, 9], la raíz 5 tiene 3 y 8 en los índices 1 y 2, y el 8 en el índice 2 tiene un espacio izquierdo vacío en 5 y el 9 en 6.

Ahora, el reflejo. La raíz permanece en el índice 0. El subárbol izquierdo de un nodo se convierte en el subárbol derecho de su copia reflejada, y su subárbol derecho se convierte en el izquierdo. Así que, si el nodo en el índice src queda en el índice dst de la respuesta, su hijo izquierdo queda en 2*dst+2 y su hijo derecho en 2*dst+1. Escribe place(src, dst): copia el valor y luego llama a place(2*src+1, 2*dst+2) y place(2*src+2, 2*dst+1). Un espacio vacío retorna de inmediato. En el primer ejemplo, el 3 en el índice 1 queda en 2, así que su hijo izquierdo 1 queda en 6 y su hijo derecho 4 en 5.

Un nodo nunca cambia de nivel, por lo que su índice reflejado permanece dentro del mismo nivel que el anterior. Redondea la longitud hacia arriba hasta completar niveles enteros (1, 3, 7, 15, ...), llena esa cantidad de espacios con -1 y elimina las entradas finales -1 al final. En el segundo ejemplo, la longitud 4 se redondea hacia arriba a 7, lo que deja espacio para el 6 en el índice 6.

Cada nodo se coloca una vez, y la salida se llena y se recorta una vez: tiempo O(n) para un arreglo de longitud n. La salida ocupa memoria O(n) y la pila de llamadas O(h), como máximo 14 marcos aquí, lo que hace que la recursión sea segura en este problema.

Algoritmo

Redondea la longitud hacia arriba a size = 2^k - 1 y rellena una salida de ese tamaño con -1.
Escribe place(src, dst): si src está más allá del final o tree[src] es -1, retorna.
De lo contrario, establece out[dst] = tree[src]; después llama a place(2*src+1, 2*dst+2) y place(2*src+2, 2*dst+1).
Llama a place(0, 0), elimina las entradas -1 finales y retorna la salida.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

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

Búsqueda en anchura con una cola de pares de índices

Intuición

Los mismos pares funcionan sin recursión. Pon (0, 0) en una cola: la raíz y el lugar al que va. Toma un par (src, dst) del principio, copia tree[src] en out[dst] y agrega a la cola cada hijo real con su destino intercambiado: el hijo izquierdo 2*src+1 con 2*dst+2, y el hijo derecho 2*src+2 con 2*dst+1.

Esta es la inversión iterativa clásica. Con objetos de nodo, tomas un nodo de la cola, intercambias sus dos hijos y los agregas a la cola. Aquí, en cambio, el intercambio se escribe en el índice de destino, porque el arreglo no puede intercambiar dos subárboles completos en un solo paso. Cada nodo real entra en la cola una vez, llevando el lugar exacto que le corresponde, así que la salida acaba teniendo cada nodo en su lugar reflejado. En el primer ejemplo, los pares resultan ser (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

El tiempo es O(n). La cola contiene como máximo un nivel y un poco más: O(w) para el nivel más ancho w, además de la salida O(n). No hay una pila de llamadas que pueda desbordarse, así que esta versión se aplica sin cambios a árboles profundos basados en punteros.

Algoritmo

Redondea la longitud al nivel entero siguiente y llena una salida de ese tamaño con -1.
Pon el par (0, 0) en una cola.
Toma un par (src, dst) del principio y establece out[dst] = tree[src].
Pon en la cola (2*src+1, 2*dst+2) y (2*src+2, 2*dst+1) por cada hijo que esté dentro del array y no sea -1.
Cuando la cola esté vacía, elimina las entradas -1 finales y devuelve la salida.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Errores comunes y casos límite

El reflejo en sí es fácil de describir. Los errores vienen del arreglo: su tamaño, su final y qué mueve realmente el intercambio de dos elementos.

Intercambiar tree[2*i+1] y tree[2*i+2] en el mismo arreglo. Eso intercambia dos valores, pero no los subárboles que hay debajo de ellos. Intercambiar los índices 1 y 2 en el primer ejemplo deja a 1 y 4 colgando debajo de 8.
Hacer que la salida tenga la misma longitud que la entrada. Un nodo reflejado puede quedar más allá del último índice de la entrada, como ocurre con 6 en el segundo ejemplo. Dimensiona la salida para que incluya niveles completos.
Olvidarse de recortar. La respuesta no tiene -1 al final, tanto para las entradas rellenadas como para los árboles cuyo reflejo termina antes que la entrada.
Invertir todo el arreglo. Eso mezcla los niveles: la última hoja se convertiría en la raíz.
Omitir la comprobación de límites. El índice de un hijo puede quedar más allá del final de la entrada, porque el arreglo puede terminar justo después del último nodo.
Confundir el desplazamiento en Lua y R, donde los arreglos empiezan en 1. Mantén los índices basados en 0 para la aritmética de 2*i+1 y lee tree[i + 1].

Preguntas frecuentes4

¿Qué significa invertir un árbol binario?

Invertir un árbol binario lo convierte en su imagen especular: en cada nodo, los subárboles izquierdo y derecho intercambian sus lugares. La raíz permanece donde está, la hoja más a la izquierda se convierte en la más a la derecha y una cadena hacia la izquierda se convierte en una cadena hacia la derecha. Invertirlo dos veces devuelve el árbol original.

¿Cuál es la complejidad temporal de invertir un árbol binario?

Cada nodo se visita una vez, por lo que el tiempo es O(n). Una solución recursiva usa O(h) de espacio en la pila para un árbol de profundidad h, y una basada en colas usa O(w) para el nivel más ancho. En esta versión con arreglos, la respuesta es un arreglo nuevo, lo que añade O(n).

¿Cómo puedes invertir un árbol binario sin usar recursión?

Usa una cola o una pila. Empieza por la raíz y, cada vez que saques un nodo, intercambia sus hijos izquierdo y derecho y vuelve a colocarlos. Cada nodo se intercambia una vez, en el orden que sea en que la estructura los vaya entregando. En la representación como arreglo, encolas pares de índices en su lugar y escribes cada nodo directamente en su posición reflejada.

¿Por qué invertir un árbol binario invierte cada nivel?

El reflejo invierte la izquierda y la derecha en todas partes, así que los nodos de cada nivel aparecen en el orden opuesto. En el almacenamiento por niveles, eso significa que se invierte cada segmento del arreglo correspondiente a un nivel: el segmento [1, 4, -1, 9] del primer ejemplo queda como [9, -1, 4, 1]. Invertir cada nivel, después de rellenar el último con -1, es una tercera solución O(n) que solo funciona con esta disposición del arreglo.

Python

def invertTree(tree):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

tree = [5, 3, 8, 1, 4, -1, 9]

Esperado

[5, 8, 3, 9, -1, 4, 1]