Maximum Depth of Binary Tree

Q: ¿Cuál es la complejidad temporal de la profundidad máxima de un árbol binario?

Cada enfoque visita cada nodo una vez, así que el tiempo es O(n) . Las versiones de búsqueda en profundidad usan O(h) de espacio adicional para la ruta actual, donde h es la profundidad. La versión de búsqueda en anchura usa O(w) para el nivel más ancho, aproximadamente la mitad de los nodos de un árbol completo.

Q: ¿Deberías usar DFS o BFS para encontrar la profundidad máxima de un árbol binario?

Ambos se ejecutan en tiempo O(n) . La búsqueda en profundidad es más breve de escribir y usa memoria proporcional a la profundidad, por lo que es adecuada para árboles anchos y poco profundos. La búsqueda en anchura cuenta directamente los niveles y usa memoria proporcional al nivel más ancho, por lo que es adecuada para árboles profundos y estrechos. Para la profundidad mínima, BFS gana porque puede detenerse en la primera hoja.

Q: ¿Cuál es la diferencia entre la profundidad y la altura de un árbol binario?

La profundidad de un nodo cuenta los pasos desde la raíz hasta él; la altura cuenta los pasos desde él hasta su hoja más profunda. La profundidad máxima del árbol es igual a la altura de la raíz. Este problema cuenta nodos, por lo que un único nodo tiene una profundidad de 1 ; contar aristas da uno menos.

FácilRecorrido de árboles

+10

Se te proporciona un árbol binario almacenado en el array tree en orden por niveles. La raíz está en el índice 0, los hijos del nodo en el índice i están en 2*i+1 (izquierdo) y 2*i+2 (derecho), -1 marca una posición vacía y el array puede terminar con entradas -1 adicionales. Devuelve la profundidad máxima del árbol: el número de nodos en el camino más largo desde la raíz hasta una hoja.

Función

maxDepth(tree: integer-array) → integer

treeinteger-array: el árbol binario en orden por niveles, con -1 para una posición vacía
Devuelveinteger: el número de nodos en el camino más largo desde la raíz hasta una hoja

Restricciones

1 ≤ tree.length ≤ 32767
Cada tree[i] es -1 o un valor con 0 ≤ tree[i] ≤ 1000.
tree[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.
Los dos hijos de un espacio vacío también están vacíos, y la profundidad es como máximo 14.

Ejemplos

Entrada: tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Salida: 4
Explicación: El camino más largo es 5, 8, 3, 6 (índices 0, 1, 4, 9), que contiene 4 nodos. El camino que pasa por 1 se detiene después de 2 nodos.

Entrada: tree = [7, -1, -1]
Salida: 1
Explicación: Las dos entradas -1 son los espacios vacíos para hijos de la raíz. La raíz por sí sola es un camino de un nodo, así que la profundidad es 1, no 0.

Entrada: tree = [2, -1, 9, -1, -1, -1, 4]
Salida: 3
Explicación: La raíz 2 no tiene hijo izquierdo. Su hijo derecho 9 en el índice 2 tiene el 4 en el índice 6 como hijo derecho, un camino de 3 nodos.

Para ir más allá

¿Cómo devolverías los valores de una ruta más larga de la raíz a una hoja, así como su longitud? Si varias rutas empatan, ¿cuál devolverías?

Pistas

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

0 de 3 abiertas

Solución

La profundidad la determina la rama más larga, y no puedes saber cuál es sin visitar todos los nodos. Así que necesitas un recorrido completo que sepa a qué profundidad está en cada nodo. La recursión, una búsqueda en anchura por niveles y una búsqueda en profundidad con tu propia pila lo hacen en una sola pasada.

Recursión en los dos subárboles

Intuición

Una posición de hijo es real cuando su índice está dentro del arreglo y su valor no es -1. El camino más profundo a través de un nodo baja hasta su subárbol más profundo, así que la profundidad en el índice i es 1 por el nodo más el mayor de las profundidades en 2*i+1 y 2*i+2. Una posición vacía tiene profundidad 0, lo que termina la recursión. Una hoja obtiene 1 + max(0, 0) = 1, y los valores suben de vuelta hasta la raíz.

Cada nodo se visita una vez. La pila de llamadas contiene un marco por cada nivel del camino actual, O(h), como máximo 14 aquí.

Algoritmo

Escribe depth(i): si i está más allá del final del arreglo o tree[i] es -1, devuelve 0.
De lo contrario, devuelve 1 + max(depth(2*i+1), depth(2*i+2)).
Devuelve depth(0).

def maxDepth(tree):
    def depth(i):
        # An index past the end or a -1 is an empty spot: depth 0.
        if i >= len(tree) or tree[i] == -1:
            return 0
        return 1 + max(depth(2 * i + 1), depth(2 * i + 2))

    return depth(0)

Búsqueda en anchura, nivel por nivel

Intuición

La profundidad máxima es el número de niveles, así que puedes contar los niveles en lugar de seguir los caminos. Una cola visita los nodos en orden por nivel. Antes de cada tanda, lee el tamaño de la cola: esos nodos corresponden exactamente a un nivel, porque los hijos que añades durante la tanda se colocan detrás de ellos. Cada tanda suma 1 a la profundidad. En el primer ejemplo, las tandas son [5], [8, 1], [3] y [6], así que la respuesta es 4.

La cola contiene un nivel a la vez, O(w) para el nivel más ancho. En un árbol completo de profundidad 14, eso representa 8192 de los 16383 nodos.

Algoritmo

Pon el índice raíz 0 en una cola y establece depth = 0.
Mientras la cola no esté vacía, suma 1 a depth y lee el tamaño de la cola.
Extrae esa cantidad de índices. Para cada uno, pon en la cola los índices de sus hijos 2*i+1 y 2*i+2 que estén dentro del arreglo y no sean -1.
Cuando la cola esté vacía, devuelve depth.

from collections import deque


def maxDepth(tree):
    n = len(tree)
    queue = deque([0])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):  # exactly the nodes of this level
            i = queue.popleft()
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
    return depth

Búsqueda en profundidad con una pila explícita

Intuición

Mantén tu propia pila de pares, un índice de nodo y su profundidad, ya que nada más recuerda a qué profundidad está un nodo. Empieza con (0, 1), la raíz en la profundidad 1. Cada nodo se apila una vez, llevando la longitud del camino que llega hasta él, así que la mayor profundidad que extraigas es la respuesta. En el primer ejemplo, el 6 se apila como (9, 4).

La pila contiene aproximadamente un hermano pendiente por nivel, O(h), sin una pila de llamadas que pueda desbordarse. El mismo código funciona con un árbol basado en punteros de cualquier profundidad.

Algoritmo

Apila (0, 1) y establece best = 0.
Extrae un par (i, depth) y establece best en el mayor de best y depth.
Para cada índice hijo 2*i+1 y 2*i+2 que esté dentro del arreglo y no sea -1, apílalo con depth + 1.
Repite hasta que la pila esté vacía y después devuelve best.

def maxDepth(tree):
    n = len(tree)
    best = 0
    stack = [(0, 1)]  # (node index, depth of that node); the root is never empty
    while stack:
        i, depth = stack.pop()
        best = max(best, depth)
        for child in (2 * i + 1, 2 * i + 2):
            if child < n and tree[child] != -1:
                stack.append((child, depth + 1))
    return best

Errores comunes y casos límite

Contar las aristas en lugar de los nodos. [7, -1, -1] tiene profundidad 1, no 0.
Omitir la comprobación de límites. En el primer ejemplo, el 6 del índice 9 tiene los índices de hijo 19 y 20, que quedan fuera del final del arreglo. Comprueba child < n antes de leer tree[child].
Calcular la profundidad a partir de la longitud del arreglo. Las entradas finales -1 llegan a un nivel sin nodos: [7, -1, -1] tiene longitud 3, pero profundidad 1.
Leer el tamaño de la cola dentro del bucle del lote. Los hijos que se añaden durante el lote lo cambian, así que guárdalo primero.
Confundir el desplazamiento en Lua y R, donde los arreglos empiezan en 1. Mantén los índices de los nodos en base 0 y lee tree[i + 1].

Preguntas frecuentes3

¿Cuál es la complejidad temporal de la profundidad máxima de un árbol binario?

Cada enfoque visita cada nodo una vez, así que el tiempo es O(n). Las versiones de búsqueda en profundidad usan O(h) de espacio adicional para la ruta actual, donde h es la profundidad. La versión de búsqueda en anchura usa O(w) para el nivel más ancho, aproximadamente la mitad de los nodos de un árbol completo.

¿Deberías usar DFS o BFS para encontrar la profundidad máxima de un árbol binario?

Ambos se ejecutan en tiempo O(n). La búsqueda en profundidad es más breve de escribir y usa memoria proporcional a la profundidad, por lo que es adecuada para árboles anchos y poco profundos. La búsqueda en anchura cuenta directamente los niveles y usa memoria proporcional al nivel más ancho, por lo que es adecuada para árboles profundos y estrechos. Para la profundidad mínima, BFS gana porque puede detenerse en la primera hoja.

¿Cuál es la diferencia entre la profundidad y la altura de un árbol binario?

La profundidad de un nodo cuenta los pasos desde la raíz hasta él; la altura cuenta los pasos desde él hasta su hoja más profunda. La profundidad máxima del árbol es igual a la altura de la raíz. Este problema cuenta nodos, por lo que un único nodo tiene una profundidad de 1; contar aristas da uno menos.

def maxDepth(tree):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

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

Salida Esperada

Maximum Depth of Binary Tree

Función

Restricciones

Ejemplos

Pistas

Solución

Recursión en los dos subárboles

Búsqueda en anchura, nivel por nivel

Búsqueda en profundidad con una pila explícita

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares