Comprobar la simetría especular
La misión
Problema
Decide si un árbol binario es la imagen especular de sí mismo, como si una línea vertical bajara por la raíz. Tanto la forma como los valores tienen que coincidir a ambos lados de esa línea. Un árbol vacío cuenta como simétrico.
Ejemplos
Input: tree = 1, left 2 with children 3 and 4, right 2 with children 4 and 3
Output: True
Por qué: el subárbol derecho es el subárbol izquierdo leído al revés
Input: tree = 1, left 2 with right child 3, right 2 with right child 3
Output: False
Por qué: los dos tres cuelgan del mismo lado, así que la forma no está reflejada
Input: tree = empty
Output: True
Por qué: caso límite: la nada es trivialmente simétrica
Pistas
0 / 3
La simetría no es una propiedad de un nodo a la vez, sino de pares de nodos que se miran de frente a través de la línea central.
Hazte una pregunta distinta de la obvia: en lugar de “¿este árbol es simétrico?”, pregunta “¿estos dos subárboles son imágenes especulares entre sí?”.
Compara como un par los subárboles izquierdo y derecho de la raíz. Dos subárboles son reflejo uno del otro cuando ambos están ausentes, o cuando ambos están presentes con valores iguales y el hijo izquierdo de uno refleja al hijo derecho del otro, en ambas direcciones.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(h)
Restricciones
- the tree may be empty
Solución
La recursión natural es sobre pares y no sobre nodos sueltos: dos subárboles son reflejo uno del otro cuando sus raíces coinciden y sus hijos se reflejan en cruz, exterior contra exterior e interior contra interior. El caso base tiene que distinguir cuando ambos están ausentes, que es una coincidencia, de cuando falta uno solo, que es una diferencia de forma, y una comparación de identidad cubre los dos casos a la vez. Cada nodo se visita una vez. El tiempo es O(n) y el espacio es O(h) para la pila de llamadas (call stack).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_symmetric(root):
def mirrors(a, b):
if a is None or b is None:
return a is b # true only when both are absent
# outer child against outer child, inner child against inner child
return (a.val == b.val and mirrors(a.left, b.right)
and mirrors(a.right, b.left))
return root is None or mirrors(root.left, root.right)
print(is_symmetric(T(1, T(2, T(3), T(4)), T(2, T(4), T(3))))) # -> True
print(is_symmetric(T(1, T(2, None, T(3)), T(2, None, T(3))))) # -> False
print(is_symmetric(None)) # -> True¿Lo que te frena es la idea y no el código? Árboles binarios lo explica.