Bottom View of Binary Tree

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

O(n) para n nodos: la búsqueda en anchura procesa cada nodo una vez con una escritura en el mapa hash. Un mapa ordenado, como un mapa de árbol, añade un factor de log w para w columnas.

MedioRecorrido de árboles Hashing

+10

El arreglo root contiene un árbol binario: la raíz en el índice 0, los hijos del índice i en 2i+1 (izquierda) y 2i+2 (derecha), -1 para una posición vacía y, posiblemente, entradas -1 adicionales al final.

La raíz está en la columna 0; un paso a la izquierda mueve una columna hacia la izquierda, y un paso a la derecha mueve una columna hacia la derecha. Visto desde abajo, cada columna muestra su nodo más profundo y, en caso de empate, el último de ese nivel al leer de izquierda a derecha (el índice mayor). Devuelve los valores que ves, empezando por la columna más a la izquierda.

Función

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

rootinteger-array: el árbol en orden de montón, con -1 para una posición vacía
Devuelveinteger-array: el valor que se ve desde abajo en cada columna, empezando por la columna 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 entradas 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, 1, 9, 6]
Explicación: La columna 0 contiene 5 y, dos niveles más abajo, 7 (índice 4) y 1 (índice 5). 1 aparece más tarde en el nivel compartido, así que se muestra. Las columnas -2, -1, 1 y 2 contienen 4, 2, 9 y 6.

Entrada: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Salida: [5, 4, 3]
Explicación: La columna -1 contiene 2 y, dos niveles más abajo, 5 (índice 9), así que ves 5. En la columna 0, 4 está debajo de la raíz. La columna 1 solo contiene 3.

Entrada: root = [8, -1, -1, -1]
Salida: [8]
Explicación: Cada posición después de la raíz es -1, así que 8 es el único nodo y la columna 0 es la única columna.

Para ir más allá

Si un empate en el nivel más profundo de una columna debe devolver todos los nodos empatados, de izquierda a derecha, ¿cómo cambiaría la versión de búsqueda en anchura? ¿Qué devolvería la columna 0 del ejemplo 1?

Solución

Cada columna muestra su nodo más profundo y, en caso de empate, gana el nodo que aparece más tarde en el recorrido por niveles. Una búsqueda en anchura visita los nodos por niveles, así que el último nodo que visita en una columna es la respuesta: haz que cada nodo sobrescriba la posición de su columna.

Recorrido en profundidad, nodo más profundo por columna

Intuición

Recorre el árbol en profundidad, asignando a cada nodo su columna y profundidad, y guarda, por columna, la profundidad y el valor del nodo más profundo encontrado hasta el momento.

Visitar el subárbol izquierdo antes que el derecho hace que encuentres los nodos de un nivel de izquierda a derecha, así que el nodo que quieres es el último encontrado: reemplaza cuando la profundidad sea mayor o igual. En el ejemplo 1, el recorrido encuentra 7 y después 1, ambos a profundidad 2 en la columna 0, y 1 ocupa la columna.

Las columnas forman un rango continuo, así que registra la menor y la mayor, y lee todas las columnas intermedias. Una visita por nodo da un tiempo de O(n), y la recursión tiene una profundidad de h llamadas para un árbol de h niveles.

Algoritmo

Visita la raíz con la columna 0 y la profundidad 0.
Omite el índice i cuando esté más allá del final del array o root[i] sea -1.
Si la columna aún no tiene un nodo, o esta profundidad es mayor o igual que la almacenada, guarda esta profundidad y el valor.
Visita 2i+1 con la columna col-1, después 2i+2 con la columna col+1, ambos un nivel más profundo.
Devuelve los valores almacenados, empezando por la columna más pequeña.

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

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace on a greater or equal depth: on a tie, the node
        # met last is the one further right, which comes later 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, último nodo por columna

Intuición

Una cola en la que cada nodo que sale añade primero su hijo izquierdo y después su hijo derecho entrega los nodos en orden por niveles: cada nodo de profundidad d antes que cualquiera de profundidad d+1, y cada nivel de izquierda a derecha. Entre los nodos de una columna, el de mayor profundidad sale último y, en caso de empate, sale el que está más a la derecha. Así que, cuando cada nodo sobrescribe la posición de su columna, cada posición termina guardando el nodo visto desde abajo, sin necesidad de comparar profundidades.

En el ejemplo 1, 7 escribe en la columna 0 y 1 lo sobrescribe.

Cada nodo requiere una visita a la cola y una escritura en el mapa: O(n) de tiempo. La cola puede contener un nivel entero, aproximadamente la mitad de los nodos, así que el espacio es O(n).

Algoritmo

Coloca el par (índice 0, columna 0) en una cola.
Extrae un par (i, col) y almacena root[i] bajo col, reemplazando cualquier valor anterior.
Añade (2i+1, col-1) y después (2i+2, col+1) por cada hijo que esté dentro del arreglo y no sea -1.
Repite hasta que la cola esté vacía, registrando la columna más pequeña y la más grande.
Devuelve los valores del mapa, empezando por la columna más pequeña.

from collections import deque


def bottomView(root):
    n = len(root)
    bottom = {}  # column -> value of the last 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 deeper nodes later, and right after left
        # on one level, so the last node to reach a column is the one seen from below.
        bottom[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 [bottom[col] for col in range(min(bottom), max(bottom) + 1)]

Errores comunes y casos límite

Reemplazar solo con una profundidad estrictamente mayor en la versión en profundidad. En el ejemplo 1, después se conserva 7 en lugar de 1.
Conservar el primer nodo que encuentra una búsqueda en anchura para cada columna. Esa es la vista superior.
Agregar el hijo derecho a la cola antes que el izquierdo. Así, cada nivel sale de derecha a izquierda y los empates se asignan al nodo equivocado.
Tomar las hojas como respuesta. En el ejemplo 1, la hoja 7 queda oculta por 1, y en el ejemplo 2 el nodo 4 tiene un hijo y, aun así, está en la parte inferior de la columna 0.
Ordenar las columnas como texto. Como cadenas, "-10" queda entre "-1" y "-2".

Preguntas frecuentes3

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

Asigna a la columna raíz el 0, a cada paso a la izquierda una columna menos y a cada paso a la derecha una más. La vista inferior enumera el nodo más profundo de cada columna, de izquierda a derecha. Este problema resuelve los empates de profundidad por orden de nivel, conservando el nodo posterior.

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

O(n) para n nodos: la búsqueda en anchura procesa cada nodo una vez con una escritura en el mapa hash. Un mapa ordenado, como un mapa de árbol, añade un factor de log w para w columnas.

¿Cuál es la diferencia entre la vista superior y la vista inferior?

Ambas eligen un nodo por columna. La vista superior elige el nodo menos profundo y la vista inferior, el más profundo. En la versión de búsqueda en anchura, la vista superior conserva el primer valor que recibe una columna; la vista inferior lo sobrescribe cada vez.

def bottomView(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, 1, 9, 6]