Maximum Depth of Binary Tree
Recibes 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 (izquierda) y 2*i+2 (derecha), -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
- treeinteger-array
- el árbol binario por niveles, con -1 para una posición vacía
- Devuelveinteger
- el número de nodos en el camino más largo de la raíz a una hoja
Restricciones
1 ≤ tree.length ≤ 32767- Cada
tree[i]es-1o un valor con0 ≤ tree[i] ≤ 1000. tree[0]nunca es-1, así que el árbol tiene al menos un nodo.- El array puede terminar con entradas
-1adicionales después del último nodo. - Ambos 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(índices0,1,4,9), que contiene 4 nodos. El camino que pasa por1se detiene después de 2 nodos.
- Entrada
- tree = [7, -1, -1]
- Salida
- 1
- Explicación
- Las dos entradas
-1son 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 es1, no0.
- Entrada
- tree = [2, -1, 9, -1, -1, -1, 4]
- Salida
- 3
- Explicación
- La raíz
2no tiene hijo izquierdo. Su hijo derecho9en el índice2tiene como hijo derecho al4en el índice6, un camino de 3 nodos.
+13 pruebas ocultas al enviar
Para ir más allá
¿Cómo devolverías los valores de un camino más largo desde la raíz hasta una hoja, y no solo su longitud? Si hay varios caminos empatados, ¿cuál devolverías y cómo lo especificarías en el contrato?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Piensa en la raíz. Si conocieras la profundidad de su subárbol izquierdo y la profundidad de su subárbol derecho, ¿cuál sería la profundidad de todo el árbol?
Es
1más la mayor de las profundidades de los dos subárboles, y un espacio vacío tiene profundidad0. La misma regla se aplica en cada nodo, así que un recorrido que conozca la profundidad de cada nodo puede encontrar la respuesta.Mantén una pila de pares, un índice de nodo y su profundidad, empezando con la raíz en profundidad 1. Extrae un par, recuerda la mayor profundidad observada y añade cada hijo en
2*i+1y2*i+2que esté dentro del arreglo y no sea-1, con la profundidad más uno.
Solución
La profundidad la determina la rama más larga, y no puedes saber cuál es sin revisar todos los nodos. Por eso, la tarea consiste en recorrer todo el árbol llevando la cuenta de la profundidad en cada nodo. La recursión, una búsqueda en anchura nivel por nivel y una búsqueda en profundidad con una pila propia lo hacen en una sola pasada; se diferencian en cómo llevan la cuenta de dónde están.
Recursión en los dos subárboles
Intuición
Primero, cómo desplazarse por el arreglo. El nodo en el índice i tiene su hijo izquierdo en 2*i+1 y su hijo derecho en 2*i+2. Un hijo existe solo si su índice está dentro del arreglo y el valor allí no es -1. En [5, 8, 1, -1, 3, -1, -1, -1, -1, 6], la raíz 5 tiene hijos en los índices 1 y 2; el 8 en el índice 1 tiene un espacio izquierdo vacío en 3 y el 3 en el índice 4 a su derecha, y ese 3 tiene debajo el 6 en el índice 9.
Ahora, la idea. El camino más profundo que pasa por un nodo desciende por el más profundo de sus dos subárboles. Así que la profundidad del subárbol en el índice i es 1 por el nodo mismo más la mayor de las profundidades en 2*i+1 y 2*i+2. Un espacio vacío tiene profundidad 0, lo que termina la recursión. Una hoja obtiene 1 + max(0, 0) = 1, y los valores ascienden hasta la raíz.
Se visita cada nodo una vez, así que el tiempo es O(n). La pila de llamadas mantiene un marco por nivel del camino actual, O(h), donde h es la profundidad, como máximo 14 aquí. Ese límite es lo que hace que la recursión sea segura en este problema. En un árbol basado en punteros con forma de cadena larga, el mismo código alcanzaría el límite de recursión, que es de 1000 marcos en Python.
Algoritmo
- Escribe
depth(i): siiestá más allá del final del array otree[i]es-1, devuelve0. - 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 del árbol, así que puedes contar los niveles en lugar de seguir los caminos. Una cola visita los nodos por niveles: empieza con la raíz y, cada vez que saques un nodo, añade sus hijos reales al final.
Para contar los niveles, procesa la cola por tandas. Antes de cada tanda, comprueba cuántos nodos contiene la cola. Esos son exactamente los nodos de un nivel, porque los hijos que añadas durante la tanda quedarán detrás de ellos. Saca esa cantidad de nodos, encola a sus hijos y suma 1 a la profundidad. Cuando la cola esté vacía, la profundidad será el número de tandas. En el primer ejemplo, las tandas son [5], [8, 1], [3] y [6], así que la respuesta es 4.
Cada nodo entra y sale de la cola una vez: tiempo O(n). La cola contiene un nivel a la vez: espacio O(w) para el nivel más ancho w. En un árbol completo, el nivel inferior contiene aproximadamente la mitad de los nodos: 8192 de los 16383 a una profundidad de 14.
Algoritmo
- Coloca el índice raíz
0en una cola y establecedepth = 0. - Mientras la cola no esté vacía, suma
1adepthy lee el tamaño de la cola. - Extrae esa cantidad de índices. Para cada uno, añade a la cola los índices de sus hijos
2*i+1y2*i+2que 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 depthBúsqueda en profundidad con una pila explícita
Intuición
Puedes recorrer caminos, como lo hace la recursión, sin hacer ni una sola llamada recursiva. Mantén tu propia pila y guarda cada nodo junto con su profundidad, ya que nada más recuerda qué tan abajo está. Empieza con el par (0, 1): la raíz, a profundidad 1.
Saca un par, compara su profundidad con la mayor vista hasta ahora y añade cada hijo real con depth + 1. Cada nodo del árbol se añade exactamente una vez, con la longitud del camino que lo alcanza, así que la mayor profundidad que saques es la respuesta. En el primer ejemplo, el 6 en el índice 9 se añade como (9, 4), y ningún par llega a más profundidad.
El tiempo es O(n). La pila contiene los hermanos pendientes a lo largo del camino actual, como máximo aproximadamente uno por nivel, así que el espacio es O(h), igual que con la recursión, pero sin una pila de llamadas que pueda desbordarse. Esta es la versión que debes elegir cuando un árbol puede ser profundo, y se aplica sin cambios a los árboles basados en punteros.
Algoritmo
- Apila
(0, 1)y establecebest = 0. - Extrae el par
(i, depth)y establecebesten el mayor debestydepth. - Para cada índice hijo
2*i+1y2*i+2que esté dentro del arreglo y no sea-1, apílalo condepth + 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
La mayoría de las respuestas incorrectas a este problema tienen un error de una unidad, o se deben a tratar un espacio vacío como si fuera un nodo.
- Contar aristas en vez de nodos. Aquí, un solo nodo tiene profundidad
1; devolver0para ese nodo, o3para un camino de 4 nodos, se queda corto por uno. - Omitir la comprobación de límites. Un nodo hoja cerca del final del arreglo puede tener índices de hijos que superen su última posición, porque el arreglo puede terminar justo después del último nodo. Comprueba
child < nantes de leertree[child]. - Leer la profundidad a partir de la longitud del arreglo. El arreglo puede tener entradas adicionales de
-1al final, por lo que su longitud puede corresponder a un nivel más profundo que el de cualquier nodo real. - Tratar
-1como un valor. Marca un nodo faltante, así que no debe añadirse a una pila ni a una cola, ni contarse. - Suponer que el árbol está equilibrado. La respuesta depende de la rama más larga, como en una cadena izquierda de 14 nodos donde todos los espacios de la derecha están vacíos.
- Leer el tamaño de la cola dentro del bucle en la versión de búsqueda en anchura. El tamaño cambia a medida que se añaden hijos, así que guárdalo antes de que empiece el lote.
- Confundir el desplazamiento en Lua y R, donde los arreglos empiezan en 1. Mantén los índices de los nodos basados en 0 para la aritmética
2*i+1y leetree[i + 1].
Preguntas frecuentes4
¿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 que se está explorando, donde h es la profundidad. La versión de búsqueda en anchura usa O(w) para el nivel más ancho, que puede contener 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 dan la respuesta correcta 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 resulta adecuada para árboles anchos y poco profundos. La búsqueda en anchura cuenta los niveles directamente y usa memoria proporcional al nivel más ancho, por lo que resulta adecuada para árboles profundos y estrechos. Para obtener la profundidad mínima, BFS tiene ventaja, porque puede detenerse en la primera hoja que encuentra.
¿Cómo encuentras la profundidad máxima de un árbol binario sin recurrencia?
Usa una pila explícita de pares: un nodo y su profundidad. Empieza con la raíz en la profundidad 1, extrae un par, registra su profundidad y agrega cada hijo con una profundidad de uno más. La profundidad máxima que extraigas es la respuesta. También funciona una cola procesada nivel por nivel, contando uno por cada nivel.
¿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, y la altura de un nodo cuenta los pasos desde él hasta su hoja más profunda. La profundidad máxima del árbol y la altura de la raíz son el mismo número. Este problema cuenta nodos, así que un único nodo tiene profundidad 1; algunos libros cuentan aristas en su lugar, lo que da un valor menos.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def maxDepth(tree):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Esperado
4