Reflejar un árbol binario
La misión
Problema
Un motor de maquetación guarda una página como un árbol binario, y los idiomas que se escriben de derecha a izquierda necesitan invertir todo el diseño. Dada la raíz de un árbol binario, intercambia los hijos izquierdo y derecho de cada nodo para que el árbol se convierta en su imagen especular, y devuelve la raíz. El árbol tiene hasta 100 nodos. Los ejemplos muestran el resultado leído nivel por nivel, de izquierda a derecha.
Ejemplos
Input: tree = 4, left 2 (children 1 and 3), right 7 (children 6 and 9)
Output: [4, 7, 2, 9, 6, 3, 1]
Por qué: ahora 7 está a la izquierda, y cada nivel se lee al revés
Input: tree = 2, left 1, right 3
Output: [2, 3, 1]
Input: tree = empty
Output: []
Por qué: caso límite: no hay nada que reflejar
Pistas
0 / 3
Reflejar todo el árbol es lo mismo que reflejar cada subárbol y luego intercambiar los dos subárboles en la raíz.
Un árbol vacío es su propio reflejo, y eso le da a la recursión su caso base.
En cada nodo, intercambia node.left y node.right, y luego refleja ambos hijos. El orden entre el intercambio y las llamadas recursivas no importa, siempre que cada nodo reciba su intercambio.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(h)
Restricciones
- n ≤ 100 nodes
Solución
El reflejo de un árbol es su raíz con el subárbol derecho reflejado a la izquierda y el subárbol izquierdo reflejado a la derecha, así que la definición ya es una recursión. Cada llamada intercambia los dos hijos de su nodo y hace la recursión en ambos; un subárbol vacío termina de inmediato. Cada nodo se intercambia exactamente una vez, así que el tiempo es O(n) y el espacio es O(h) para la recursión en un árbol de altura h.
from collections import deque
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def mirror(node):
if node is None:
return None
node.left, node.right = mirror(node.right), mirror(node.left) # swap flipped halves
return node
def levels(root):
out, q = [], deque([root] if root else [])
while q:
node = q.popleft()
out.append(node.val)
q.extend(c for c in (node.left, node.right) if c)
return out
print(levels(mirror(T(4, T(2, T(1), T(3)), T(7, T(6), T(9)))))) # -> [4, 7, 2, 9, 6, 3, 1]
print(levels(mirror(T(2, T(1), T(3))))) # -> [2, 3, 1]
print(levels(mirror(None))) # -> []¿Lo que te frena es la idea y no el código? Árboles binarios lo explica.