Symmetric Tree

Q: ¿Cuál es la complejidad temporal de Symmetric Tree?

Cada nodo real se compara una vez, como parte de un par simétrico, por lo que el tiempo es O(n) . Las versiones recursiva y con pila utilizan espacio adicional O(h) para los pares pendientes a lo largo del camino actual. La versión nivel por nivel mantiene un nivel en memoria, O(w) para el nivel más ancho.

Q: ¿Cómo compruebas si un árbol binario es simétrico sin recurrir a la recursividad?

Mantén una pila o una cola de pares de nodos que deben reflejarse entre sí, empezando por los dos hijos de la raíz. Saca un par, falla si no coinciden y añade el par exterior y el par interior de sus hijos. Si la pila queda vacía sin que haya discrepancias, el árbol es simétrico.

Q: ¿Cuál es la diferencia entre un árbol simétrico y dos árboles idénticos?

Dos árboles son idénticos cuando comparas el izquierdo con el izquierdo y el derecho con el derecho. Un árbol es simétrico cuando su subárbol izquierdo es idéntico a la imagen especular de su subárbol derecho, por lo que la comparación se cruza: el izquierdo con el derecho y el derecho con el izquierdo. El mismo código para comprobar pares resuelve ambos problemas intercambiando los pares de hijos.

Q: ¿Es simétrico un árbol con un solo nodo?

Sí. Un solo nodo tiene dos espacios vacíos para hijos, y dos espacios vacíos se reflejan entre sí. Una raíz con exactamente un hijo nunca es simétrica, porque ese hijo se enfrenta a un espacio vacío.

FácilRecorrido de árboles

+10

Se te proporciona un árbol binario almacenado en el array tree en orden por niveles. La raíz está en el índice 0, los hijos del nodo en el índice i están en 2*i+1 (izquierda) y 2*i+2 (derecha), -1 marca una posición vacía y el array puede terminar con entradas -1 adicionales. Devuelve true si el árbol es una imagen especular de sí mismo respecto a una línea vertical que pasa por la raíz, y false en caso contrario. Tanto la forma como los valores deben coincidir.

Función

isSymmetric(tree: integer-array) → boolean

treeinteger-array: el árbol binario por niveles, con -1 para las posiciones vacías
Devuelveboolean: verdadero si el árbol es simétrico, falso en caso contrario

Restricciones

1 ≤ tree.length ≤ 32767
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 = [1, 2, 2, 3, 4, 4, 3]
Salida: true
Explicación: Pliega el árbol por la mitad. Los dos 2 de los índices 1 y 2 se encuentran, los 3 exteriores de los índices 3 y 6 se encuentran, y los 4 interiores de los índices 4 y 5 se encuentran.

Entrada: tree = [1, 2, 2, -1, 3, -1, 3]
Salida: false
Explicación: Ambos 3 cuelgan a la derecha de sus padres. En una imagen especular, el hijo derecho del 2 izquierdo (índice 4) debe estar frente al hijo izquierdo del 2 derecho (índice 5), y el índice 5 está vacío.

Entrada: tree = [4, 6, 6, 5, -1, -1, 9]
Salida: false
Explicación: La forma es una imagen especular: el índice 3 se enfrenta al índice 6 y ambos contienen un nodo. Sus valores son distintos, 5 frente a 9, así que el árbol no es simétrico.

+16 pruebas ocultas al enviar

Para ir más allá

Si la forma se refleja a sí misma, pero algunos valores no, ¿cuál es el menor número de valores de nodos que debes cambiar para que el árbol sea simétrico?

Pistas

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

0 de 3 abiertas

Solución

La simetría es una propiedad de los pares. Cada nodo tiene una pareja en el punto reflejado al otro lado de la raíz, y la pareja de un hijo izquierdo es un hijo derecho. Así que nunca comparas un nodo con sus propios hijos: recorres las dos mitades del árbol en direcciones opuestas al mismo tiempo, comparas la forma y el valor de cada par y te detienes en el primer par que no coincide.

Compara cada nivel con su reverso

Intuición

Primero, cómo desplazarse 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 es real solo si su índice está dentro del arreglo y el valor allí no es -1. En [1, 2, 2, 3, 4, 4, 3], la raíz 1 tiene sus hijos en los índices 1 y 2, y el 2 en el índice 1 tiene sus hijos en 3 y 4.

Ahora observa el árbol nivel por nivel. Una imagen especular se lee igual de izquierda a derecha que de derecha a izquierda, así que cada nivel, escrito con sus espacios vacíos, debe leerse igual en ambas direcciones. En el primer ejemplo, los niveles debajo de la raíz se leen 2 2 y 3 4 4 3. En el segundo se leen 2 2 y después -1 3 -1 3, que al invertirse queda 3 -1 3 -1, así que la respuesta es false.

Los espacios vacíos deben permanecer en la fila. Sin ellos, el nivel inferior del segundo ejemplo se leería 3 3 y cumpliría la condición. Escribe una entrada por cada posición de hijo de cada nodo real del nivel, -1 para una posición vacía; los hijos de las posiciones vacías también están vacíos, así que no añaden nada. Cada nodo se visita una vez, por lo que el tiempo es O(n), y se mantiene en memoria un nivel a la vez, O(w) para el nivel más ancho w.

Algoritmo

Empieza con una lista que contenga el índice raíz 0.
Para cada índice de la lista, de izquierda a derecha, anota ambos lugares de los hijos: el valor del hijo si existe, -1 si está vacío. Recopila los hijos reales para el siguiente nivel.
Si esa fila de lugares de los hijos difiere de su reverso, devuelve false.
Pasa al siguiente nivel y repite hasta que esté vacío; después, devuelve true.

def isSymmetric(tree):
    n = len(tree)
    level = [0]  # the real nodes of one level, left to right
    while level:
        row = []  # the child spots under this level, -1 for an empty one
        next_level = []
        for i in level:
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    row.append(tree[child])
                    next_level.append(child)
                else:
                    row.append(-1)
        if row != row[::-1]:
            return False
        level = next_level
    return True

Recursión en pares reflejados

Intuición

En lugar de comparar niveles completos, compara dos subárboles: el subárbol izquierdo de la raíz, que empieza en el índice 1, y su subárbol derecho, que empieza en el índice 2. Dos posiciones son simétricas cuando ambas están vacías o cuando ambas contienen el mismo valor y sus hijos se cruzan. El hijo izquierdo de una corresponde al hijo derecho de la otra (el par exterior), y el hijo derecho de una corresponde al hijo izquierdo de la otra (el par interior).

En el primer ejemplo, mirrors(1, 2) compara los dos 2, después llama a mirrors(3, 6) para los 3 exteriores y a mirrors(4, 5) para los 4 interiores. Cada una de esas llamadas solo encuentra posiciones vacías debajo y devuelve true. En el segundo ejemplo, mirrors(4, 5) encuentra un 3 en el índice 4 frente a una posición vacía en el índice 5, devuelve false y el false sube hasta la raíz.

Cada nodo real pertenece como máximo a un par, así que el tiempo es O(n). La pila de llamadas tiene una profundidad igual a la del árbol, O(h), que aquí es de como máximo 14 marcos.

Algoritmo

Escribe mirrors(a, b). Una posición está vacía cuando su índice supera el final o contiene -1. Si ambas posiciones están vacías, devuelve true; si solo una lo está, devuelve false.
Si tree[a] y tree[b] son diferentes, devuelve false.
De lo contrario, devuelve mirrors(2*a+1, 2*b+2) y mirrors(2*a+2, 2*b+1).
Devuelve mirrors(1, 2). Una raíz sin hijos da dos posiciones vacías, lo que es true.

def isSymmetric(tree):
    n = len(tree)

    def mirrors(a, b):
        # Spots a and b must hold the same value, or both be empty.
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a or empty_b:
            return empty_a and empty_b
        return (tree[a] == tree[b]
                and mirrors(2 * a + 1, 2 * b + 2)   # outer pair
                and mirrors(2 * a + 2, 2 * b + 1))  # inner pair

    return mirrors(1, 2)

Pila explícita de pares reflejados

Intuición

La recursión solo necesita una cosa: los pares que aún esperan ser comprobados. Mantén esos pares en una pila propia y las llamadas desaparecerán. Empieza con el par (1, 2). Extrae un par. Si ambas posiciones están vacías, no hay nada debajo de ellas, así que continúa. Si una está vacía o los valores son distintos, el árbol no es simétrico. De lo contrario, inserta el par exterior (2*a+1, 2*b+2) y el par interior (2*a+2, 2*b+1).

El orden en que compruebas los pares no importa, porque el árbol es simétrico solo si todos los pares coinciden. Una pila sigue un orden en profundidad; una cola seguiría un orden por niveles y funcionaría igual. El tercer ejemplo se detiene en el primer par incorrecto, (3, 6), que contiene 5 y 9.

Cada extracción procesa un par y cada nodo real forma parte de como máximo un par, así que el tiempo es O(n). La pila conserva aproximadamente un par pendiente por cada nivel del recorrido actual, lo que requiere un espacio de O(h), y no hay que preocuparse por ningún límite de recursión.

Algoritmo

Apila el par (1, 2) en una pila.
Desapila un par (a, b). Si ambas posiciones están vacías (el índice está fuera del final o es -1), pasa al siguiente par.
Si solo una posición está vacía, o tree[a] difiere de tree[b], devuelve false.
Apila (2*a+1, 2*b+2) y (2*a+2, 2*b+1).
Cuando la pila esté vacía, devuelve true.

def isSymmetric(tree):
    n = len(tree)
    stack = [(1, 2)]  # pairs of spots that must mirror each other
    while stack:
        a, b = stack.pop()
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a and empty_b:
            continue
        if empty_a or empty_b or tree[a] != tree[b]:
            return False
        stack.append((2 * a + 1, 2 * b + 2))  # outer pair
        stack.append((2 * a + 2, 2 * b + 1))  # inner pair
    return True

Errores comunes y casos límite

La mayoría de las respuestas incorrectas comparan el par de nodos equivocado o olvidan que un espacio vacío forma parte de la estructura.

Comprobar cada subárbol por separado. El subárbol izquierdo no tiene que ser simétrico por sí mismo: en [1, 2, 2, 3, 4, 4, 3], el subárbol 2, 3, 4 no lo es, pero el árbol completo sí. Debe reflejar el subárbol derecho.
Emparejar los hijos de forma incorrecta. El hijo izquierdo de un lado se corresponde con el hijo derecho del otro: (2*a+1, 2*b+2) y (2*a+2, 2*b+1), nunca (2*a+1, 2*b+1).
Comparar solo los valores. Si quitas los espacios vacíos de [1, 2, 2, -1, 3, -1, 3], todas las filas de cada nivel se leen igual en ambos sentidos, pero el árbol no es simétrico. Conserva -1 en la fila del nivel o comprueba si hay espacios vacíos en la prueba de pares.
Leer más allá del final. Un índice que supera el final del arreglo es un espacio vacío. Comprueba a < n antes de leer tree[a]; un árbol con un solo nodo no tiene ningún índice 1 ni 2.
Detenerse en el primer par coincidente. Un solo par correcto no demuestra nada; devuelve true solo después de comprobar todos los pares.
Confundir el desplazamiento en Lua y R, donde los arreglos comienzan en 1. Mantén los índices de los nodos basados en 0 para la operación aritmética 2*i+1 y lee tree[i + 1].

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Symmetric Tree?

Cada nodo real se compara una vez, como parte de un par simétrico, por lo que el tiempo es O(n). Las versiones recursiva y con pila utilizan espacio adicional O(h) para los pares pendientes a lo largo del camino actual. La versión nivel por nivel mantiene un nivel en memoria, O(w) para el nivel más ancho.

¿Cómo compruebas si un árbol binario es simétrico sin recurrir a la recursividad?

Mantén una pila o una cola de pares de nodos que deben reflejarse entre sí, empezando por los dos hijos de la raíz. Saca un par, falla si no coinciden y añade el par exterior y el par interior de sus hijos. Si la pila queda vacía sin que haya discrepancias, el árbol es simétrico.

¿Cuál es la diferencia entre un árbol simétrico y dos árboles idénticos?

Dos árboles son idénticos cuando comparas el izquierdo con el izquierdo y el derecho con el derecho. Un árbol es simétrico cuando su subárbol izquierdo es idéntico a la imagen especular de su subárbol derecho, por lo que la comparación se cruza: el izquierdo con el derecho y el derecho con el izquierdo. El mismo código para comprobar pares resuelve ambos problemas intercambiando los pares de hijos.

¿Es simétrico un árbol con un solo nodo?

Sí. Un solo nodo tiene dos espacios vacíos para hijos, y dos espacios vacíos se reflejan entre sí. Una raíz con exactamente un hijo nunca es simétrica, porque ese hijo se enfrenta a un espacio vacío.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

tree = [1, 2, 2, 3, 4, 4, 3]

Esperado

true

Symmetric Tree

Función

Restricciones

Ejemplos

Pistas

Solución

Compara cada nivel con su reverso

Recursión en pares reflejados

Pila explícita de pares reflejados

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares