Vertical Order Traversal of a Binary Tree

DifícilRecorrido de árboles Ordenación Hashing

+10

Un árbol binario se almacena en 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), -1 marca una posición vacía y el arreglo puede terminar con entradas adicionales -1.

La raíz está en la columna 0; un hijo izquierdo está una columna a la izquierda de su padre y un hijo derecho, una columna a la derecha. Devuelve una lista por columna, de izquierda a derecha. Dentro de cada columna, lista los nodos de arriba abajo y, entre los nodos que comparten una columna y una profundidad, en orden creciente de valor.

Función

verticalTraversal(root: integer-array) → integer-2d-array

rootinteger-array: el árbol en orden de heap, con -1 para una posición vacía
Devuelveinteger-2d-array: una lista de valores por columna, empezando por la columna situada más a la izquierda y siguiendo de arriba abajo

Restricciones

1 ≤ root.length ≤ 32767
Cada root[i] es -1 o un valor con 0 ≤ root[i] ≤ 5000, 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 -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 = [5, 2, 9, 4, 7, 1, 6]
Salida: [[4], [2], [5, 1, 7], [9], [6]]
Explicación: La columna 0 contiene la raíz 5; después, 7 y 1 dos niveles más abajo. Esos dos comparten columna y profundidad, así que 1 aparece antes que 7, aunque 7 está más a la izquierda.

Entrada: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Salida: [[2, 5], [1, 4], [3]]
Explicación: La columna -1 contiene 2 a profundidad 1 y 5 a profundidad 3 (el hijo izquierdo de 4). La columna 0 contiene la raíz 1 y 4 en el índice 4. La columna 1 contiene solo 3.

Entrada: root = [6, -1, -1]
Salida: [[6]]
Explicación: 6 no tiene hijos, así que la respuesta tiene una sola columna, [6].

Para ir más allá

Todos los valores son como máximo 5000. ¿Puedes aprovechar eso para prescindir del ordenamiento por comparación y terminar en O(n + 5000) tiempo?

Solución

Cada nodo tiene tres claves: columna, profundidad y valor. La respuesta son los nodos ordenados por esas claves, una lista por columna. En los empates en columna y profundidad, se ordenan por valor, no según el orden de izquierda a derecha en que los encuentra un recorrido, así que debes ordenarlos: todos los nodos a la vez o cada nivel de una búsqueda en anchura.

Registra cada nodo y, después, ordénalos

Intuición

Visita cada nodo una vez, en cualquier orden, y registra la terna (columna, profundidad, valor). Un paso hacia un hijo suma 1 a la profundidad y mueve la columna 1 a la izquierda o a la derecha. Después, ordena las ternas por columna, profundidad y valor. Ahora, los nodos de cada columna quedan juntos, en el orden requerido. Recorre la lista ordenada y empieza una nueva lista interna cada vez que cambie la columna.

En el ejemplo 1, las ternas de la columna 0 se ordenan así: (0, 0, 5), (0, 2, 1), (0, 2, 7). La ordenación, O(n log n), domina el recorrido O(n), y las ternas ocupan un espacio O(n).

Algoritmo

Coloca (índice 0, columna 0, profundidad 0) en una pila.
Extrae un nodo, registra (columna, profundidad, valor) y coloca cada hijo real con columna col-1 o col+1 y profundidad depth+1.
Cuando la pila esté vacía, ordena las ternas por columna, después por profundidad y luego por valor.
Recórrelas, iniciando una lista nueva cada vez que cambie la columna.

def verticalTraversal(root):
    n = len(root)
    entries = []  # (column, depth, value) for every node
    stack = [(0, 0, 0)]  # (node index, column, depth); the root is never empty
    while stack:
        i, col, depth = stack.pop()
        entries.append((col, depth, root[i]))
        for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
            if child < n and root[child] != -1:
                stack.append((child, child_col, depth + 1))
    # Column, then depth, then value: exactly the order of the answer.
    entries.sort()
    result = []
    for k, (col, depth, value) in enumerate(entries):
        if k == 0 or col != entries[k - 1][0]:
            result.append([])  # a new column starts
        result[-1].append(value)
    return result

Nivel por nivel, ordena dentro de cada nivel

Intuición

Una búsqueda en anchura procesa un nivel a la vez. Si cada nodo añade su valor a la lista de su columna cuando se procesa, todas las listas ya están ordenadas de arriba abajo, así que no hace falta ordenar por profundidad. Los empates solo se producen dentro de un mismo nivel, así que ordena cada nivel por columna y luego por valor antes de procesarlo.

En el ejemplo 1, el nivel 2 llega como 4, 7, 1, 6 en las columnas -2, 0, 0, 2 y se ordena como 4, 1, 7, 6, por lo que la columna 0 queda como [5, 1, 7]. Las columnas ocupadas forman un rango continuo, así que basta con llevar la cuenta de la menor y la mayor.

Ordenar un nivel de m nodos cuesta O(m log m). El peor caso sigue siendo O(n log n), porque el último nivel de un árbol completo contiene aproximadamente la mitad de los nodos. El espacio es O(n).

Algoritmo

Empieza con un nivel que contenga (índice 0, columna 0).
Ordena el nivel por columna y después por valor.
En ese orden, añade cada valor a la lista de su columna y recopila sus hijos reales, con las columnas col-1 y col+1, en el siguiente nivel.
Repite hasta que un nivel esté vacío, haciendo un seguimiento de la columna más pequeña y la más grande.
Devuelve las listas desde la columna más pequeña hasta la más grande.

def verticalTraversal(root):
    n = len(root)
    columns = {}  # column -> its values, top to bottom
    level = [(0, 0)]  # (node index, column) of every node on the current level
    while level:
        # Every node here has the same depth: order them by column, then value.
        level.sort(key=lambda node: (node[1], root[node[0]]))
        next_level = []
        for i, col in level:
            columns.setdefault(col, []).append(root[i])
            for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
                if child < n and root[child] != -1:
                    next_level.append((child, child_col))
        level = next_level
    # The columns that hold a node form one unbroken range.
    return [columns[col] for col in range(min(columns), max(columns) + 1)]

Errores comunes y casos límite

Dejar los empates en orden de izquierda a derecha. Una búsqueda en anchura sin ordenar por nivel da [5, 7, 1] para la columna 0 del ejemplo 1, no [5, 1, 7].
Agregar valores durante un recorrido en profundidad sin ordenar. En [1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5], un recorrido primero por la izquierda agrega 5 (profundidad 3) a la columna 1 antes que 3 (profundidad 1).
Ordenar por columna y valor, pero no por profundidad. La columna 0 del ejemplo 1 queda entonces como [1, 5, 7].
Usar cadenas como claves de las columnas. Ordenadas como texto, "-1" aparece antes que "-2", así que las columnas a la izquierda de 0 quedan en el orden incorrecto.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del recorrido en orden vertical de un árbol binario?

Ordenar todos los nodos por columna, profundidad y valor cuesta O(n log n) y domina el recorrido O(n). Ordenar nivel por nivel tiene el mismo caso peor, porque el último nivel de un árbol completo contiene aproximadamente la mitad de los nodos. El espacio es O(n).

¿Se puede realizar el recorrido en orden vertical sin ordenar?

Solo si los empates se ordenan de izquierda a derecha. Después, una búsqueda en anchura que agrega cada valor a la lista de su columna da la respuesta en O(n). Si los empates se ordenan por valor, necesitas ordenar, pero solo dentro de un nivel, ya que solo pueden empatar los nodos de un mismo nivel.

¿Qué relación tiene el recorrido en orden vertical con la vista superior y la vista inferior?

Las tres vistas agrupan los nodos por los mismos números de columna. La vista superior conserva el nodo más superficial de cada columna, y la vista inferior, el más profundo. El recorrido en orden vertical conserva todos los nodos y, cuando varios comparten un nivel, los ordena por valor, mientras que las vistas eligen según la posición.

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