Top View of Binary Tree

Q: ¿Cuál es la complejidad temporal de la vista superior de un árbol binario?

Una búsqueda en anchura visita cada uno de los n nodos una vez, con una búsqueda en el mapa de O(1) por nodo, por lo que se ejecuta en tiempo O(n) si registras la columna más pequeña y la más grande. Un mapa ordenado de columnas hace que la complejidad sea O(n log w) para w columnas.

MedioRecorrido de árboles Hashing

+10

Recibes un árbol binario almacenado en el arreglo root en orden de montículo: la raíz en el índice 0, los hijos del índice i en 2*i+1 (izquierdo) y 2*i+2 (derecho), y -1 para una posición vacía.

La raíz está en la columna 0; un hijo izquierdo se encuentra una columna a la izquierda de su padre y un hijo derecho, una columna a la derecha. Visto desde arriba, se ve el nodo más superficial de cada columna; en caso de empate, el que aparece primero en su nivel de izquierda a derecha (el índice menor). Devuelve los valores que ves, desde la columna más a la izquierda hasta la más a la derecha.

Función

topView(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 visto desde arriba en cada columna, empezando por la columna situada más a la izquierda

Restricciones

1 ≤ root.length ≤ 32767
Cada root[i] es -1 o un valor con 0 ≤ root[i] ≤ 10⁴, y ningún valor aparece dos veces.
root[0] nunca es -1, así que el árbol tiene al menos un nodo.
El arreglo puede terminar con elementos adicionales -1 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 = [5, 2, 9, 4, 7, 1, 6]
Salida: [4, 2, 5, 9, 6]
Explicación: De izquierda a derecha, las columnas contienen 4 (columna -2), 2 (-1), la raíz 5 (0), 9 (1) y 6 (2). 7 y 1 también están en la columna 0, pero la raíz está por encima de ellos.

Entrada: root = [1, 2, -1, -1, 3, -1, -1, -1, -1, -1, 4]
Salida: [2, 1, 4]
Explicación: 2 está en la columna -1. Su hijo derecho 3, en el índice 4, vuelve a estar en la columna 0, debajo de la raíz, así que está oculto. 4, en el índice 10, el hijo derecho de 3, está solo en la columna 1.

Entrada: root = [6, -1, -1]
Salida: [6]
Explicación: Los índices 1 y 2 contienen -1, así que 6 queda solo en la columna 0 y constituye toda la vista.

Para ir más allá

Con objetos de nodo en lugar de un arreglo, no hay ningún índice para resolver un empate. ¿Cómo expresarías la regla para los empates y cambiaría tu código de búsqueda en anchura?

Solución

Cada columna muestra su nodo más superficial y, en caso de empate, el primero en el orden por niveles. Ese es exactamente el orden en que una búsqueda en anchura visita los nodos, así que el primer nodo que encuentra la búsqueda en una columna es la respuesta. También funciona un recorrido en profundidad, pero debe llevar un registro de las profundidades y resolver los empates con cuidado.

Recorrido en profundidad, nodo menos profundo por columna

Intuición

Recorre el árbol en profundidad con la columna y la profundidad de cada nodo, y guarda, para cada columna, la profundidad y el valor del nodo menos profundo encontrado hasta el momento.

Reemplaza solo si la profundidad es estrictamente menor. De dos nodos empatados, el que aparece primero en el orden por niveles se alcanza primero en un recorrido que explora cada subárbol izquierdo antes que el derecho correspondiente, porque cuando los dos caminos se separan, va hacia la izquierda. Reemplazar cuando la profundidad es igual hace que gane el nodo posterior: con el índice 3 vacío y nodos en los índices 19 y 23, ambos están en la columna -2, en la profundidad 4, y la respuesta es el nodo del índice 19.

Las columnas ocupadas forman un rango ininterrumpido, ya que un nodo en la columna -3 tiene antepasados en las columnas -1 y -2, así que lleva un seguimiento de la columna más pequeña y la más grande. Cada nodo se visita una vez, tiempo O(n), y la recursión tiene una profundidad de aproximadamente h llamadas.

Algoritmo

Visita la raíz con la columna 0 y la profundidad 0. Regresa de inmediato si el índice está fuera del arreglo o contiene -1.
Si la columna aún no tiene ningún nodo, o esta profundidad es estrictamente menor que la almacenada, guarda esta profundidad y este valor.
Visita 2i+1 con la columna col-1, después 2i+2 con la columna col+1, un nivel más abajo.
Devuelve los valores almacenados desde la columna más pequeña hasta la más grande.

def topView(root):
    n = len(root)
    best = {}  # column -> (depth, value) of the shallowest node found so far

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace only on a strictly smaller depth: on a tie, the node
        # met first is the one further left, which comes first in level order.
        if col not in best or depth < best[col][0]:
            best[col] = (depth, root[i])
        visit(2 * i + 1, col - 1, depth + 1)
        visit(2 * i + 2, col + 1, depth + 1)

    visit(0, 0, 0)
    # The columns that hold a node form one unbroken range.
    return [best[col][1] for col in range(min(best), max(best) + 1)]

Primero en anchura, primer nodo por columna

Intuición

Una cola que toma la raíz, después el hijo izquierdo de cada nodo y después su hijo derecho, libera los nodos en orden por niveles: todos los nodos de profundidad d antes que cualquier nodo de profundidad d+1, y cada nivel de izquierda a derecha. Esa es la prioridad del problema, así que el primer nodo que recibe una columna es el que se ve desde arriba, y todos los posteriores se omiten.

Cada nodo cuesta una búsqueda en el mapa, O(n) en total. La cola puede contener un nivel completo, hasta aproximadamente la mitad de los nodos, así que el espacio es O(n).

Algoritmo

Coloca el par (índice 0, columna 0) en una cola.
Saca un par (i, col). Si el mapa no tiene una entrada para col, guarda root[i] allí.
Añade (2i+1, col-1) y después (2i+2, col+1), por cada hijo que exista.
Cuando la cola esté vacía, devuelve los valores del mapa desde la columna más pequeña hasta la más grande.

from collections import deque


def topView(root):
    n = len(root)
    top = {}  # column -> value of the first node seen in that column
    queue = deque([(0, 0)])  # (node index, column); the root is never empty
    while queue:
        i, col = queue.popleft()
        # The queue hands out shallower nodes first, and left before right
        # on one level, so the first node of a column is the one seen from above.
        if col not in top:
            top[col] = root[i]
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and root[left] != -1:
            queue.append((left, col - 1))
        if right < n and root[right] != -1:
            queue.append((right, col + 1))
    # The columns that hold a node form one unbroken range.
    return [top[col] for col in range(min(top), max(top) + 1)]

Errores comunes y casos límite

Conservar el primer nodo que encuentra un recorrido en profundidad. Si el hijo izquierdo de la raíz tiene un hijo derecho que a su vez tiene un hijo derecho (columna 1, profundidad 3), el recorrido lo encuentra antes que al hijo derecho de la raíz (columna 1, profundidad 1).
Encolar primero el hijo derecho: los empates se resuelven a favor del nodo equivocado.
Ordenar las columnas como texto: "-1" se ordena antes que "-2".
Suponer que el subárbol izquierdo ocupa las columnas negativas. En el ejemplo 2, el nodo 4 está en el subárbol izquierdo de la raíz y en la columna 1.

Preguntas frecuentes3

¿Qué es la vista superior de un árbol binario?

Numera las columnas desde la raíz empezando por 0: una menos para un hijo izquierdo y una más para un hijo derecho. La vista superior enumera, para cada columna de izquierda a derecha, el nodo más cercano a la raíz.

¿Cuál es la complejidad temporal de la vista superior de un árbol binario?

Una búsqueda en anchura visita cada uno de los n nodos una vez, con una búsqueda en el mapa de O(1) por nodo, por lo que se ejecuta en tiempo O(n) si registras la columna más pequeña y la más grande. Un mapa ordenado de columnas hace que la complejidad sea O(n log w) para w columnas.

¿En qué se diferencia la vista superior de la vista izquierda y la vista inferior?

La vista izquierda selecciona el primer nodo de cada nivel. La vista superior selecciona el nodo menos profundo de cada columna. La vista inferior selecciona el nodo más profundo de cada columna, así que una búsqueda en anchura para obtenerla sobrescribe cada columna en lugar de conservar el primer nodo.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

root = [5, 2, 9, 4, 7, 1, 6]

Salida Esperada

[4, 2, 5, 9, 6]