Binary Tree Zigzag Level Order Traversal
Tienes un árbol binario almacenado en el arreglo root. La raíz está en el índice 0, los hijos del índice i están en 2*i+1 (izquierda) y 2*i+2 (derecha), -1 marca una posición vacía y el arreglo puede terminar con entradas -1 adicionales.
Devuelve los valores de los nodos nivel por nivel en orden zigzag: el nivel de la raíz de izquierda a derecha, el siguiente de derecha a izquierda, y así sucesivamente, alternando hasta el nivel más profundo. Esto también se conoce como recorrido en espiral por niveles.
Función
- rootinteger-array
- el árbol en orden de heap, con -1 para una posición vacía
- Devuelveinteger-2d-array
- una lista de valores por nivel, primero el nivel superior, alternando entre izquierda a derecha y derecha a izquierda
Restricciones
1 ≤ root.length ≤ 32767- Cada
root[i]es-1o un valor con0 ≤ root[i] ≤ 104. - Los valores de los nodos son distintos.
root[0]nunca es-1, así que el árbol tiene al menos un nodo.- La matriz puede terminar con entradas
-1adicionales después del último nodo. - Ambos hijos de un espacio vacío también están vacíos, y el árbol tiene como máximo
14niveles.
Ejemplos
- Entrada
- root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
- Salida
- [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
- Explicación
- Leídos de izquierda a derecha, los niveles son
8;12, 5;1, 9, 14;4, 2, 11. Los niveles 1 y 3 se recorren hacia atrás:[5, 12]y[11, 2, 4].
- Entrada
- root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
- Salida
- [[1], [3, 2], [4, 5, 6, 7]]
- Explicación
- Un árbol completo de tres niveles: el nivel intermedio se invierte a
[3, 2]y el tercero vuelve a recorrer de izquierda a derecha. Las dos entradas finales-1son los lugares vacíos para los hijos de4.
- Entrada
- root = [5]
- Salida
- [[5]]
- Explicación
- Un nodo individual es un nivel de un valor, leído en cualquier dirección.
Para ir más allá
¿Puedes colocar cada valor directamente en su lugar final de su fila, sin invertir nada ni usar una segunda pila?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Recopila primero los niveles, cada uno de izquierda a derecha, como en un recorrido por niveles normal. ¿Cuáles de esas listas deben cambiar y cómo?
Numera los niveles desde 0 en la raíz. Los niveles impares se leen al revés. Invertir una lista cuesta tanto como leerla, así que invertir esos niveles mantiene todo en tiempo lineal.
Para omitir la inversión, mantén el nivel actual en una pila y coloca los hijos en una segunda pila mientras los vas sacando: primero el hijo izquierdo cuando lees de izquierda a derecha, y primero el hijo derecho cuando lees de derecha a izquierda. Después, al sacar elementos de la segunda pila, obtienes el siguiente nivel en el orden que necesitas.
Solución
Los niveles provienen de una búsqueda en anchura ordinaria. La parte nueva es la dirección: cada dos niveles salen invertidos. Invierte las filas impares después de construirlas o guarda cada nivel en una pila, que devuelve los elementos en el orden opuesto al de las inserciones.
Orden por niveles y luego invertir niveles alternos
Intuición
Una cola que procesa un nivel por ronda produce cada nivel de izquierda a derecha. Numera los niveles desde 0 en la raíz: el recorrido en zigzag lee los niveles impares de derecha a izquierda, así que invertir exactamente esas filas da la respuesta.
La búsqueda visita cada nodo una vez y cada inversión vuelve a recorrer cada valor una vez, así que el tiempo es O(n).
Algoritmo
- Inicia una cola con el índice
0. - En cada ronda, guarda la longitud de la cola
s, desencolasíndices en una nueva fila y encola los hijos existentes de cada uno, primero el izquierdo y luego el derecho. - Si la respuesta ya contiene un número impar de filas, invierte la fila.
- Agrega la fila y continúa hasta que la cola esté vacía.
from collections import deque
def zigzagLevelOrder(root):
n = len(root)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(root[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
if len(levels) % 2 == 1: # levels 1, 3, 5, ... read from right to left
row.reverse()
levels.append(row)
return levelsDos pilas
Intuición
Mantén el nivel actual en una pila que se desapila en la dirección en que se lee el nivel, y apila los hijos de cada nodo desapilado en una segunda pila. Cuando la pila actual se vacía, la segunda contiene el siguiente nivel.
El orden de apilado hace que funcione. Al desapilar de izquierda a derecha, apila primero el hijo izquierdo de cada nodo y luego el derecho: el hijo derecho del nodo situado más a la derecha se apila en último lugar, así que el siguiente nivel se desapila desde su extremo derecho. Al desapilar de derecha a izquierda, apila primero el hijo derecho y luego el izquierdo, y el hijo izquierdo del nodo situado más a la izquierda se apila en último lugar.
Ejemplo 1: desapila 8, apila 12, 5. Desapila 5, 12, luego apila 14 desde 5 y 9, 1 desde 12. Desapila 1, 9, 14, luego apila 4, 2 desde 9 y 11 desde 14. Desapila 11, 2, 4.
Cada nodo se apila y se desapila una vez: tiempo O(n), sin una pasada de inversión.
Algoritmo
- Coloca el índice
0de la raíz en una pila y empieza a leer de izquierda a derecha. - Mientras la pila no esté vacía, extrae cada índice y colócalo en una nueva fila, y coloca los hijos existentes de cada nodo extraído en una segunda pila: primero el izquierdo y luego el derecho al leer de izquierda a derecha; en caso contrario, primero el derecho y luego el izquierdo.
- Añade la fila a la respuesta.
- Convierte la segunda pila en la pila actual, invierte la dirección y repite.
def zigzagLevelOrder(root):
n = len(root)
levels = []
current = [0] # a stack of node indexes; the root is never empty
left_to_right = True
while current:
row = []
upcoming = [] # the next level, pushed while this one pops
while current:
i = current.pop()
row.append(root[i])
# Push so that the next level pops out in its own direction.
if left_to_right:
children = (2 * i + 1, 2 * i + 2)
else:
children = (2 * i + 2, 2 * i + 1)
for child in children:
if child < n and root[child] != -1:
upcoming.append(child)
levels.append(row)
current = upcoming
left_to_right = not left_to_right
return levels
Errores comunes y casos límite
- Invertir el orden en el que los hijos entran en una sola cola. Los hermanos intercambian sus posiciones, pero los padres mantienen su orden: el tercer nivel del ejemplo 1 queda como
[9, 1, 14]. - Contar los niveles desde 1. Cada inversión queda desplazada un nivel, y el ejemplo 1 da
[[8], [12, 5], [14, 9, 1], [4, 2, 11]]. - Usar el mismo orden de inserción en cada nivel de la versión con dos pilas. Después, el tercer nivel del ejemplo 1 se extrae como
[9, 1, 14]. - Apilar los hijos en la pila de la que todavía estás extrayendo elementos. Se extraen antes que el resto del nivel de su padre.
- Ordenar una fila en vez de invertirla. El último nivel del ejemplo 1 debe ser
[11, 2, 4], que ningún ordenamiento produce.
Preguntas frecuentes3
¿Cuál es la diferencia entre el recorrido en zigzag y el recorrido por niveles?
Recorren los mismos niveles con los mismos nodos. El recorrido por niveles lee cada nivel de izquierda a derecha; el recorrido en zigzag lee cada segundo nivel de derecha a izquierda, comenzando por el nivel debajo de la raíz. Ambos se ejecutan en O(n) tiempo.
¿El recorrido en zigzag es lo mismo que el recorrido en espiral de un árbol?
Sí, los dos nombres describen el mismo recorrido. Algunos textos empiezan el segundo nivel por la izquierda en lugar de por la derecha, lo que solo desplaza los cambios de dirección un nivel. Aquí, el nivel de la raíz va de izquierda a derecha y el siguiente, de derecha a izquierda.
¿Se puede realizar el recorrido por niveles en zigzag con una deque?
Sí. Mantén cada nivel de la deque en orden de izquierda a derecha. En un nivel de izquierda a derecha, toma los nodos del frente y agrega sus hijos, primero el izquierdo y después el derecho, al final. En un nivel de derecha a izquierda, toma los nodos del final y agrega sus hijos, primero el derecho y después el izquierdo, al frente. La cantidad que tomas al comenzar una ronda sigue marcando el nivel.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def zigzagLevelOrder(root):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Salida Esperada
[[8], [5, 12], [1, 9, 14], [11, 2, 4]]