Left View of Binary Tree

+10

Obtienes un árbol binario como el arreglo root en orden de heap: 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), y -1 marca un espacio vacío. El arreglo puede terminar con entradas adicionales -1.

Párate a la izquierda del árbol. En cada nivel ves un nodo, el más a la izquierda; el resto del nivel queda oculto detrás de él. Devuelve los valores que ves, desde el nivel superior hacia abajo.

Función

leftView(root: integer-array) → integer-array

rootinteger-array: el árbol en orden de montículo, con -1 para un espacio vacío
Devuelveinteger-array: el valor más a la izquierda de cada nivel, empezando por el nivel superior

Restricciones

1 ≤ root.length ≤ 32767
Cada root[i] es -1 o un valor con 0 ≤ root[i] ≤ 10⁴.
Los valores de los nodos son distintos.
root[0] nunca es -1, así que el árbol tiene al menos un nodo.
El arreglo puede terminar con entradas -1 adicionales 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 14 niveles.

Ejemplos

Entrada: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Salida: [3, 8, 6, 1]
Explicación: 8 es una hoja, así que el tercer y cuarto nivel contienen solo 6 (índice 6) y 1 (índice 13), ambos bajo el hijo derecho 5. Aun así, puedes verlos: [3, 8, 6, 1].

Entrada: root = [10, -1, -1]
Salida: [10]
Explicación: Los índices 1 y 2 contienen -1, así que 10 no tiene hijos y la vista muestra solo la raíz.

Entrada: root = [1, 2, 3, 4, 5, 6, 7]
Salida: [1, 2, 4]
Explicación: Un árbol completo de tres niveles. Las posiciones más a la izquierda de los niveles son los índices 0, 1 y 3, que contienen 1, 2 y 4.

Para ir más allá

Nivel d llena los índices 2^d-1 a 2^(d+1)-2. ¿Puedes construir la vista recorriendo esos rangos, sin usar una cola ni recursión? ¿Qué costo tiene en un arreglo rellenado?

Solución

Seguir los hijos izquierdos desde la raíz falla cuando el subárbol izquierdo es más corto: en el primer ejemplo, los niveles inferiores se ven a través del subárbol derecho. Quieres el primer nodo de cada nivel. La búsqueda en anchura te entrega cada nivel de izquierda a derecha; un recorrido en profundidad que empieza por la izquierda encuentra primero el nodo más a la izquierda de cada nivel.

Primero en anchura, primer nodo de cada nivel

Intuición

Una cola procesada por rondas te da los niveles de uno en uno. Al comienzo de una ronda, la cola contiene exactamente un nivel, de izquierda a derecha, porque cada hijo añadido durante la ronda queda detrás de él. Extrae esa cantidad de índices, encola los hijos de cada uno, empezando por la izquierda, y conserva el primer valor.

En el primer ejemplo, las rondas son [3], [8, 5], [6] y [1], y conservan 3, 8, 6 y 1. El 8 no añade nada, porque sus posiciones de hijo 3 y 4 contienen -1.

Cada nodo entra y sale de la cola una vez: tiempo O(n). La cola contiene un nivel completo, hasta 8192 índices en un árbol completo de 14 niveles.

Algoritmo

Inicia una cola que contenga el índice 0 y una respuesta vacía.
Mientras la cola no esté vacía, sea s su tamaño y elimina s índices. Añade el valor del primero.
Por cada índice eliminado i, añade a la cola 2i+1 y después 2i+2, omitiendo los índices que superen el final y las entradas iguales a -1.

from collections import deque


def leftView(root):
    n = len(root)
    view = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        size = len(queue)  # exactly the nodes of the current level
        for j in range(size):
            i = queue.popleft()
            if j == 0:
                view.append(root[i])  # the first node of this level
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
    return view

En profundidad primero, empezando por el hijo izquierdo

Intuición

Recorre el árbol en profundidad, visitando el subárbol izquierdo antes que el derecho, y pasa la profundidad de cada nodo. El primer nodo al que llega el recorrido en la profundidad d es el más a la izquierda del nivel d. Toma el nodo más a la izquierda x de un nivel y cualquier nodo y a su derecha: en el último nodo que comparten sus caminos, x va a la izquierda y y a la derecha, y el recorrido termina la rama izquierda antes de girar a la derecha.

El recorrido baja un nivel cada vez, así que cuando llega por primera vez a la profundidad d, la respuesta contiene exactamente d valores. Registra un nodo cuando d es igual a la longitud de la respuesta; no hace falta ningún conjunto de profundidades visitadas.

Cada nodo se visita una vez: tiempo O(n), y la memoria contiene una llamada por nivel, como máximo 14 en este caso. La versión de R mantiene su propia pila y apila el hijo derecho antes que el izquierdo.

Algoritmo

Crea una respuesta vacía y llama a visit(0, 0).
En visit(i, d), retorna inmediatamente si i</code está fuera del array o si <code>root[i] es -1.
Si d es igual a la longitud de la respuesta, el recorrido ha llegado al nivel d por primera vez: añade root[i].
Llama a visit(2i+1, d+1), después a visit(2i+2, d+1).
Devuelve la respuesta una vez que termina la primera llamada.

def leftView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

Errores comunes y casos límite

Seguir únicamente los hijos izquierdos desde la raíz. En el primer ejemplo, eso se detiene en 8 y pasa por alto 6 y 1.
Leer la primera posición de cada nivel, root[2^d-1]. En el primer ejemplo, la primera posición del tercer nivel, índice 3, contiene -1, mientras que su único nodo está en el índice 6.
Visitar primero el hijo derecho en el recorrido en profundidad. El primer nodo visitado en cada nivel es entonces el más a la derecha.
Leer un hijo sin comprobar los límites. El 1 en el índice 13 tiene posiciones para hijos 27 y 28, que quedan fuera del arreglo de 14 elementos.

Preguntas frecuentes3

¿La vista izquierda es igual que el límite izquierdo de un árbol?

No. El límite izquierdo es un recorrido: comienza en el hijo izquierdo de la raíz, va hacia la izquierda cuando puede; de lo contrario, hacia la derecha, y se detiene antes de una hoja. La vista izquierda toma un nodo por nivel de cualquier rama. En el primer ejemplo, el límite está vacío, ya que 8 es una hoja, pero la vista muestra 8, 6 y 1.

¿Cuál es la complejidad temporal y espacial de la vista izquierda?

Ambas soluciones visitan cada nodo una vez, así que el tiempo es O(n). La cola de búsqueda en anchura contiene un nivel completo, aproximadamente la mitad de los nodos de un árbol completo. El recorrido primero por la izquierda mantiene una llamada por nivel, O(h) para h niveles.

¿Cómo cambias la solución para obtener la vista correcta?

En la versión de búsqueda en anchura, conserva el último valor de cada ronda en lugar del primero. En la versión de búsqueda en profundidad, visita el hijo derecho antes que el izquierdo; así, el primer nodo que alcanza el recorrido en cada nivel es el más a la derecha.

def leftView(root):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Salida Esperada

[3, 8, 6, 1]