Binary Tree Level Order Traversal
El array tree contiene un árbol binario. 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 puede haber entradas -1 adicionales al final.
Devuelve los valores de los nodos nivel por nivel: una lista por nivel, desde la raíz hasta el nivel más profundo, cada una con sus valores de izquierda a derecha.
Función
- treeinteger-array
- el árbol en orden de montículo, con -1 para una posición vacía
- Devuelveinteger-2d-array
- una lista de valores por nivel, primero el nivel superior y, dentro de cada nivel, de izquierda a derecha
Restricciones
1 ≤ tree.length ≤ 32767- Cada
tree[i]es-1o un valor con0 ≤ tree[i] ≤ 1000. tree[0]nunca es-1, así que el árbol tiene al menos un nodo.- El arreglo puede terminar con entradas adicionales
-1despué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 = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
- Salida
- [[4], [9, 2], [6, 8, 5], [3]]
- Explicación
- El índice 3 está vacío, así que
9solo tiene un hijo derecho,6. El tercer nivel es6,8,5, y el3en el índice 9, debajo de6, está solo en el cuarto nivel.
- Entrada
- tree = [7, -1, -1]
- Salida
- [[7]]
- Explicación
- Ambos hijos de la raíz son
-1, así que el árbol es el nodo único7y tiene un nivel.
- Entrada
- tree = [1, 3, -1, 5, -1, -1, -1]
- Salida
- [[1], [3], [5]]
- Explicación
- Cada nodo tiene solo un hijo izquierdo:
3en el índice 1 y5en el índice 3. Cada nivel contiene un valor, y las entradas finales-1no añaden nada.
Para ir más allá
¿Puedes devolver los niveles en orden de zigzag, el primero de izquierda a derecha, el segundo de derecha a izquierda, y así sucesivamente, sin ordenar ningún nivel?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Los hijos del índice
ise encuentran en2*i+1y2*i+2. Si siempre visitas primero los nodos más cercanos a la raíz y avanzas de izquierda a derecha entre ellos, ¿en qué orden te encuentras con los nodos?Una cola devuelve los nodos en el orden en que los agregaste. Si agregas los hijos de un nodo cuando lo sacas, los nodos salen de a un nivel por vez. Lo que queda es indicar dónde termina un nivel y comienza el siguiente.
Al comienzo de cada ronda, la cola contiene exactamente un nivel. Lee su tamaño
s, sacasnodos y colócalos en una lista nueva, y añade sus hijos, primero el izquierdo, omitiendo-1y los índices que superen el final. Detente cuando la cola esté vacía.
Solución
Cada nivel debe quedar como su propia lista de izquierda a derecha. Una búsqueda en anchura con una cola visita los nodos en ese orden y, al comienzo de cada ronda, la cola contiene exactamente un nivel, así que su tamaño indica cuántos nodos hay que tomar. También sirve un recorrido en profundidad que lleve un registro de la profundidad de cada nodo.
Búsqueda en profundidad, clasificada por profundidad
Intuición
Recorre el árbol en profundidad, pasando a cada nodo su profundidad, 0 para la raíz, y mantén una lista por cada profundidad. Un nodo a profundidad d añade su valor a la lista d, iniciando esa lista si es el primer nodo que se encuentra en su nivel.
Cada lista queda ordenada de izquierda a derecha porque el recorrido termina el subárbol izquierdo de un nodo antes de entrar en el derecho. De dos nodos en un mismo nivel, se alcanza primero aquel cuyo camino gira a la izquierda donde se separan los caminos. En el ejemplo 1, el orden de visita 4, 9, 6, 3, 2, 8, 5 completa [4], [9, 2], [6, 8, 5], [3].
Cada nodo se visita una vez: tiempo O(n), con una recursión tan profunda como el árbol, hasta 14 niveles.
Algoritmo
- Crea una lista vacía de niveles.
- Visita la raíz con profundidad 0.
- En el nodo
icon profundidadd, detente siiestá más allá del final o sitree[i]es-1. - Si solo hay
dlistas, agrega una vacía. Añadetree[i]a la listad. - Visita
2i+1y después2i+2, ambos con profundidadd+1.
def levelOrder(tree):
n = len(tree)
levels = []
def visit(i, depth):
if i >= n or tree[i] == -1:
return
if depth == len(levels): # the first node seen on this level
levels.append([])
levels[depth].append(tree[i])
# Left before right, so every level fills from left to right.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return levelsBúsqueda en anchura, un nivel por ronda
Intuición
Saca un nodo de la cola y añade sus hijos, primero el izquierdo. El nivel d+1 entra solo cuando sale el nivel d, así que los nodos salen nivel por nivel, de izquierda a derecha.
Para dividir esa secuencia en niveles, lee el tamaño de la cola al inicio de una ronda. El nivel anterior ya salió y todavía no ha llegado ninguno del siguiente, así que la cola contiene exactamente el nivel actual. Toma esa cantidad de nodos para formar una fila; sus hijos esperan a la siguiente ronda. En el ejemplo 1, las rondas toman 1, 2, 3 y 1 nodos.
Cada nodo entra y sale de la cola una vez: tiempo O(n). La cola contiene aproximadamente un nivel, como máximo 8,192 nodos en el nivel más profundo de un árbol completo de 14 niveles.
Algoritmo
- Pon el índice
0de la raíz en una cola. - Mientras la cola no esté vacía, lee su tamaño
se inicia una fila vacía. - Saca
síndices. Para cada índicei, añadetree[i]a la fila. - Añade
2i+1y después2i+2a la cola cuando el índice esté dentro del arreglo y no contenga-1. - Añade la fila a la respuesta e inicia la siguiente ronda.
from collections import deque
def levelOrder(tree):
n = len(tree)
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(tree[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
levels.append(row)
return levels
Errores comunes y casos límite
- Leer el tamaño de la cola mientras la vacías. En
while (j < queue.length), la longitud aumenta a medida que llegan los hijos, así que el siguiente nivel se filtra en la fila actual. - Añadir el hijo derecho antes que el izquierdo, o visitar primero el subárbol derecho. El segundo nivel del ejemplo 1 se lee entonces
[2, 9]. - Omitir la comprobación del límite
child < n. Los hijos de los nodos más profundos quedan fuera del final de la matriz. - Eliminar elementos del principio de una lista basada en una matriz simple, lo que en muchos lenguajes desplaza toda la cola cada vez. Usa una cola real o un índice de cabecera.
- Tratar
-1como un nodo. Nunca entra en una fila ni en la cola:[7, -1, -1]da[[7]], no[[7], []].
Preguntas frecuentes3
¿Cuál es la complejidad temporal del recorrido por niveles de un árbol binario?
Ambas soluciones visitan cada nodo una vez: tiempo O(n) para n nodos. La respuesta contiene n valores, así que el espacio es O(n). Además, la cola contiene aproximadamente tantos elementos como el nivel más ancho y la recursión, la altura del árbol.
¿Cómo sabes dónde termina un nivel en una búsqueda en anchura?
Lee el tamaño de la cola al comienzo de cada ronda y toma exactamente esa cantidad de nodos. También funcionan otras dos formas: mantener el nivel actual y el siguiente en dos listas separadas, o insertar un marcador en la cola después de cada nivel.
El arreglo ya está almacenado nivel por nivel. ¿Por qué no leerlo en segmentos?
Para este formato funciona así: el nivel d, con la raíz en 0, ocupa los índices 2^d-1 a 2^(d+1)-2, así que recopila los valores no vacíos de cada rango hasta que un rango no tenga ninguno. En las entrevistas normalmente se pasan objetos de nodo con punteros; solo la cola se mantiene en esa forma.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def levelOrder(tree):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Salida Esperada
[[4], [9, 2], [6, 8, 5], [3]]