Binary Tree Level Order Traversal

Q: ¿Cuál es la complejidad temporal del recorrido por niveles de un árbol binario?

Tanto la solución de búsqueda en anchura como la de búsqueda en profundidad visitan cada nodo una vez, así que se ejecutan en tiempo O(n) para n nodos. La respuesta en sí contiene n valores, así que el espacio es O(n) . Además, la cola contiene como máximo aproximadamente el nivel más ancho, y la recursión, como máximo, la altura del árbol.

Q: ¿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. En ese momento, la cola contiene exactamente los nodos de un nivel, así que sacar esa cantidad de nodos extrae el nivel y nada más. También funcionan otras dos formas: mantener el nivel actual y el siguiente en dos listas separadas, o insertar un marcador después de cada nivel.

Q: ¿Se puede realizar un recorrido por niveles con una búsqueda en profundidad?

Sí. Pasa a cada nodo su profundidad y añade su valor a la lista de esa profundidad. Mientras el recorrido visite el subárbol izquierdo antes que el derecho, todas las listas quedan en orden de izquierda a derecha. También es O(n) ; la búsqueda en anchura encaja mejor porque produce los niveles en orden.

Q: El arreglo ya está almacenado nivel por nivel. ¿Por qué no leerlo en segmentos?

Para este formato funciona lo siguiente: el nivel d ocupa los índices 2^d-1 a 2^(d+1)-2 , así que puedes recopilar los valores no vacíos de cada rango y detenerte en el primer rango que no tenga ninguno. Sin embargo, en una entrevista, el árbol suele venir como objetos nodo con punteros izquierdo y derecho, y sin índices para dividirlo. El recorrido basado en una cola es lo que se puede aplicar a ese formato y a variantes como el orden en zigzag o la vista del lado derecho.

MedioRecorrido de árboles Cola

+10

Recibes un árbol binario almacenado en el array tree. La raíz está en el índice 0, los hijos del nodo en el índice i están en 2*i+1 (izquierdo) y 2*i+2 (derecho), -1 marca una posición vacía y el array puede terminar con entradas -1 adicionales.

Devuelve los valores de los nodos nivel por nivel: una lista con el valor de la raíz, luego una lista con los valores del nivel inmediatamente inferior, de izquierda a derecha, y así sucesivamente hasta el nivel más profundo.

Función

levelOrder(tree: integer-array) → integer-2d-array

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, cada uno de izquierda a derecha

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 elementos -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 = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Salida: [[4], [9, 2], [6, 8, 5], [3]]
Explicación: La raíz 4 tiene como hijos a 9 y 2 en los índices 1 y 2. El índice 3 está vacío, así que el tercer nivel es 6 (índice 4, debajo de 9), luego 8 y 5 (índices 5 y 6, debajo de 2). El 3 del índice 9 es el hijo izquierdo de 6, 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 único 7 y 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: 3 en el índice 1 y 5 en el índice 3. Cada nivel contiene un valor, y las entradas finales -1 no añaden nada.

+15 pruebas ocultas al enviar

Para ir más allá

¿Puedes devolver los niveles en orden 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.

0 de 3 abiertas

Solución

Cada nivel debe salir como su propia lista, ordenado de izquierda a derecha. Una búsqueda en anchura con una cola visita los nodos exactamente en ese orden. La única idea adicional es saber dónde termina un nivel: al inicio de cada ronda, la cola contiene todo el nivel actual y nada más, así que su tamaño te indica cuántos nodos debes tomar. Un recorrido en profundidad también funciona, siempre que lleve la profundidad de cada nodo y vaya primero a la izquierda y luego a la derecha.

En profundidad, ordenado por profundidad

Intuición

Primero, recorramos el arreglo. El hijo izquierdo del índice i está en 2i+1 y el hijo derecho, en 2i+2. Falta un hijo cuando su índice está más allá del final del arreglo o contiene -1. En el ejemplo 1, los hijos de 9 (índice 1) están en los índices 3 y 4, que contienen -1 y 6, así que 9 solo tiene un hijo derecho.

Ahora recorre el árbol en profundidad y pasa a cada nodo su profundidad, que es 0 para la raíz. Mantén una lista por profundidad. Cuando llegues a un nodo de profundidad d, añade su valor a la lista d; si hasta ahora solo hay d listas, este es el primer nodo de un nuevo nivel, así que primero inicia una lista nueva.

¿Por qué queda cada nivel ordenado de izquierda a derecha? El recorrido termina todo el subárbol izquierdo de un nodo antes de entrar en el subárbol derecho. Toma dos nodos del mismo nivel: en el punto donde se separan sus caminos desde la raíz, uno va a la izquierda y el otro a la derecha, y el recorrido llega primero al de la izquierda. En el ejemplo 1, el orden es 4, 9, 6, 3, 2, 8, 5, lo que llena las listas así: [4], [9, 2], [6, 8, 5], [3].

Cada nodo se visita una vez, así que el tiempo es O(n) para n nodos, y las listas contienen n valores. La recursión solo alcanza la profundidad del árbol, que aquí es de 15 niveles como máximo. La versión de R usa en su lugar una pila explícita; primero apila el hijo derecho y luego el izquierdo, para que el izquierdo salga primero, y después agrupa los valores por profundidad con split.

Algoritmo

Crea una lista vacía de niveles.
Visita la raíz con profundidad 0.
En el nodo i con profundidad d, detente si i está más allá del final o si tree[i] es -1.
Si solo hay d listas, añade una vacía. Añade tree[i] a la lista d.
Visita 2i+1 y después 2i+2, ambos con profundidad d+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 levels

En anchura, un nivel por ronda

Intuición

Una cola devuelve los valores en el orden en que entraron. Introduce la raíz. Después, saca repetidamente un nodo e introduce sus hijos, primero el hijo izquierdo. Cada nodo del nivel d+1 entra en la cola cuando su padre del nivel d sale de ella, así que todos los nodos del nivel d salen antes de que salga cualquiera del nivel d+1 y, dentro de un nivel, los nodos salen de izquierda a derecha.

Esto produce un flujo de valores en orden por niveles. Para dividirlo en niveles, lee el tamaño de la cola al comienzo de una ronda. En ese momento, la cola contiene exactamente el nivel actual: el nivel anterior ya salió y ninguno de los nodos del siguiente nivel ha llegado todavía. Saca esa cantidad de nodos y colócalos en una lista. Los hijos que añadan pertenecerán a la ronda siguiente.

En el ejemplo 1, la cola empieza como [4]: saca 1 nodo, fila [4], y entran 9, 2. Saca 2 nodos, fila [9, 2], y entran 6, 8, 5. Saca 3, fila [6, 8, 5], y entra 3. Saca 1, fila [3], y la cola queda vacía.

Cada nodo entra y sale de la cola una vez, así que el tiempo es O(n). La cola contiene como máximo aproximadamente un nivel, hasta 16384 nodos en el nivel más profundo de un árbol completo de profundidad 14. Usa una cola real o un índice de cabecera: sacar el primer elemento de una lista de arreglos simple desplaza todos los elementos que le siguen en muchos lenguajes.

Algoritmo

Pon el índice 0 de la raíz en una cola.
Mientras la cola no esté vacía, lee su tamaño s e inicia una fila vacía.
Saca s índices. Para cada índice i, agrega tree[i] a la fila.
Agrega 2i+1 y después 2i+2 a la cola cuando el índice esté dentro del arreglo y no contenga -1.
Agrega 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

El recorrido en sí es corto. Los errores están en los límites de los niveles y en los espacios vacíos.

Leer el tamaño de la cola mientras todavía la estás vaciando. En un bucle como while (j < queue.length), la longitud aumenta a medida que llegan los hijos, así que el siguiente nivel se filtra en la fila actual. Lee el tamaño una vez, antes de que empiece la ronda.
Añadir el hijo derecho antes que el izquierdo. Así, cada nivel queda de derecha a izquierda. Lo mismo ocurre con un recorrido en profundidad que visita primero el subárbol derecho.
Tratar -1 como un valor. Un espacio vacío no es un nodo, así que nunca entra en una fila ni en la cola.
Olvidar la comprobación de límites. Los hijos de los nodos más profundos pueden quedar más allá del final del arreglo, así que comprueba child < n antes de leer tree[child].
Devolver niveles vacíos. Las entradas -1 finales no contienen nodos, así que la respuesta para [7, -1, -1] es [[7]], no [[7], []].

Preguntas frecuentes4

¿Cuál es la complejidad temporal del recorrido por niveles de un árbol binario?

Tanto la solución de búsqueda en anchura como la de búsqueda en profundidad visitan cada nodo una vez, así que se ejecutan en tiempo O(n) para n nodos. La respuesta en sí contiene n valores, así que el espacio es O(n). Además, la cola contiene como máximo aproximadamente el nivel más ancho, y la recursión, como máximo, 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. En ese momento, la cola contiene exactamente los nodos de un nivel, así que sacar esa cantidad de nodos extrae el nivel y nada más. También funcionan otras dos formas: mantener el nivel actual y el siguiente en dos listas separadas, o insertar un marcador después de cada nivel.

¿Se puede realizar un recorrido por niveles con una búsqueda en profundidad?

Sí. Pasa a cada nodo su profundidad y añade su valor a la lista de esa profundidad. Mientras el recorrido visite el subárbol izquierdo antes que el derecho, todas las listas quedan en orden de izquierda a derecha. También es O(n); la búsqueda en anchura encaja mejor porque produce los niveles en orden.

El arreglo ya está almacenado nivel por nivel. ¿Por qué no leerlo en segmentos?

Para este formato funciona lo siguiente: el nivel d ocupa los índices 2^d-1 a 2^(d+1)-2, así que puedes recopilar los valores no vacíos de cada rango y detenerte en el primer rango que no tenga ninguno. Sin embargo, en una entrevista, el árbol suele venir como objetos nodo con punteros izquierdo y derecho, y sin índices para dividirlo. El recorrido basado en una cola es lo que se puede aplicar a ese formato y a variantes como el orden en zigzag o la vista del lado derecho.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]

Esperado

[[4], [9, 2], [6, 8, 5], [3]]