Binary Tree Right Side View

Q: ¿Cuál es la complejidad temporal y espacial de la vista del lado derecho de un árbol binario?

El tiempo es O(n) para n nodos, y ninguna solución puede omitir nodos, ya que el nodo más a la derecha de un nivel puede estar en cualquier lugar. El espacio es O(w) para la cola, donde w es el nivel más ancho, o O(h) para el recorrido primero por la derecha en un árbol de h niveles.

MedioRecorrido de árboles Cola

+10

El arreglo root contiene un árbol binario. La raíz se encuentra en el índice 0, los hijos del nodo en el índice i se encuentran en 2*i+1 (izquierda) y 2*i+2 (derecha), -1 marca un espacio vacío y puede haber entradas adicionales -1 al final.

Mira el árbol desde su lado derecho. Cada nivel te muestra exactamente un nodo, el que está más a la derecha, y oculta el resto. Enumera esos valores desde el nivel de la raíz hasta el más profundo.

Función

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

rootinteger-array: el árbol en orden de heap, con -1 para una posición vacía
Devuelveinteger-array: el valor situado más a la derecha 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 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, 7, 4, -1, 1, -1, 3]
Salida: [5, 9, 1, 3]
Explicación: Desde la derecha ves 5, 9 y 1 (índice 6). El cuarto nivel solo contiene 3, en el índice 8, debajo de 7 en el subárbol izquierdo. Nada en la derecha llega tan profundo, así que 3 es visible.

Entrada: root = [6, 0, -1, 8, -1, -1, -1]
Salida: [6, 0, 8]
Explicación: El árbol es una cadena de hijos izquierdos: 6, 0, 8. Cada nivel contiene un nodo, así que ves los tres, aunque ninguno de ellos es un hijo derecho.

Entrada: root = [42]
Salida: [42]
Explicación: Un arreglo de longitud 1: la raíz 42 no tiene ningún espacio para hijos, y la vista es ese único valor.

Para ir más allá

¿Cómo obtendrías la vista del lado derecho de un árbol en el que cada nodo puede tener cualquier cantidad de hijos, almacenados en una lista de izquierda a derecha?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Ves el nodo más a la derecha de cada nivel, y no tiene por qué ser un hijo derecho: el último valor del ejemplo 1 está en el subárbol izquierdo. Una búsqueda en anchura hace que ese nodo sea el último de cada ronda; un recorrido en profundidad que va primero a la derecha lo encuentra antes que a cualquier otro nodo de su nivel.

Recorrido en anchura, último nodo de cada nivel

Intuición

Procesa el árbol un nivel por ronda. Cuando comienza una ronda, la cola contiene exactamente un nivel, de izquierda a derecha, así que el último índice que sacas de la cola en la ronda es el nodo más a la derecha de ese nivel, y su valor se añade a la respuesta.

En el ejemplo 1, las rondas son [5], [2, 9], [7, 4, 1] y [3], y sus últimas entradas dan 5, 9, 1, 3. Lo que decide es el nivel, no el lado: 3 cuelga del subárbol izquierdo, pero está solo en su nivel.

Cada índice se añade y se saca de la cola una vez, así que el tiempo es O(n). La cola crece hasta alcanzar el nivel más ancho: O(n) en el peor caso.

Algoritmo

Encola el índice raíz 0.
Inicia una ronda guardando la longitud de la cola s.
Desencola s índices. Para cada índice i, encola 2i+1 y después 2i+2 si son menores que la longitud del arreglo y no son -1.
Agrega el valor del último índice desencolado en la ronda.
Repite hasta que la cola esté vacía y luego devuelve la respuesta.

from collections import deque


def rightSideView(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 == size - 1:
                view.append(root[i])  # the last 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, hijo derecho primero

Intuición

Recorre el árbol en profundidad, probando el hijo derecho antes que el izquierdo, y lleva la profundidad, que es 0 en la raíz. La primera vez que el recorrido alcanza la profundidad d, la respuesta contiene exactamente d valores. Añade el valor del nodo en ese momento e ignora todos los nodos posteriores de ese nivel.

Ese primer nodo es el que está más a la derecha: siempre que dos caminos hacia un nivel se separan, el recorrido sigue la rama derecha hasta el fondo antes de retroceder hacia la izquierda. En el ejemplo 1, el recorrido visita 5, 9, 1, 2, 4, 7, 3: omite 2, 4 y 7, cuyas profundidades ya tienen un valor, y añade 3.

Cada nodo se visita una vez; el tiempo es O(n), con una llamada por nivel en la pila, como máximo 14.

Algoritmo

Empieza con una respuesta vacía y la raíz en la profundidad 0.
Omite un índice que esté más allá del final del arreglo o contenga -1.
Cuando la longitud de la respuesta sea igual a la profundidad, agrega el valor: el recorrido ha llegado a un nuevo nivel, y llegó a él desde la derecha.
Recorre primero el hijo derecho 2i+2 y después el hijo izquierdo 2i+1, cada uno un nivel más profundo.
Devuelve la respuesta.

def rightSideView(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])
        # Right before left, so the rightmost node of every level comes first.
        visit(2 * i + 2, depth + 1)
        visit(2 * i + 1, depth + 1)

    visit(0, 0)
    return view

Errores comunes y casos límite

Seguir únicamente los hijos derechos desde la raíz. El ejemplo 1 da [5, 9, 1] y omite 3; el ejemplo 2 da [6].
Leer la última posición de cada nivel, root[2^(d+1)-2]. En el ejemplo 2, el índice 6 contiene -1; el nodo visible es 8 en el índice 3.
Omitir la comprobación de longitud en la posición de un hijo. En el ejemplo 1, 3 es la última entrada, por lo que sus posiciones de hijos 17 y 18 no existen.
Encolar primero el hijo derecho y conservar el último nodo de cada ronda. Así se obtiene la vista izquierda, [5, 2, 7, 3].
Permitir que los nodos posteriores sobrescriban a los anteriores en el recorrido de derecha a izquierda, lo que también da como resultado la vista izquierda.

Preguntas frecuentes3

¿Cuál es la complejidad temporal y espacial de la vista del lado derecho de un árbol binario?

El tiempo es O(n) para n nodos, y ninguna solución puede omitir nodos, ya que el nodo más a la derecha de un nivel puede estar en cualquier lugar. El espacio es O(w) para la cola, donde w es el nivel más ancho, o O(h) para el recorrido primero por la derecha en un árbol de h niveles.

¿Puede resolverlo una búsqueda en profundidad que priorice la izquierda?

Sí, si sobrescribes en lugar de conservar el primer valor. Un recorrido de izquierda a derecha visita los nodos de cada nivel de izquierda a derecha, así que almacena el valor de cada nodo a su profundidad y deja que los nodos posteriores reemplacen a los anteriores. Cada profundidad termina con su valor más a la derecha. Sigue siendo O(n), pero escribe una vez por nodo.

¿Debería usar una búsqueda en anchura o en profundidad aquí?

Ambos son lineales. La búsqueda en anchura sigue la definición, un nivel por ronda. La búsqueda en profundidad conserva solo la ruta actual, lo que ahorra memoria en un árbol ancho, y su forma recursiva ocupa unas pocas líneas menos.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

root = [5, 2, 9, 7, 4, -1, 1, -1, 3]

Salida Esperada

[5, 9, 1, 3]