Profundidad mínima hasta una hoja
La misión
Problema
Dada la raíz de un árbol binario, devuelve la cantidad de nodos del camino más corto de la raíz a una hoja, donde una hoja es un nodo sin hijos. Un árbol vacío tiene profundidad 0. Un nodo con un solo hijo no es una hoja, así que un camino que pasa por él tiene que continuar hacia ese hijo.
Ejemplos
Input: tree = 6, left 2 (whose left is 1, whose left is 0), right 9
Output: 2
Por qué: 9 es una hoja un paso por debajo de la raíz
Input: tree = 1, right 2, whose right is 3
Output: 3
Por qué: 1 y 2 tienen un hijo cada uno, así que solo 3 es una hoja
Input: tree = empty
Output: 0
Por qué: caso límite: no hay nodos
Pistas
0 / 3
La hoja menos profunda podría estar en cualquier lado, pero nunca puede estar más abajo que la primera hoja que encuentras al explorar el árbol nivel por nivel.
Explora un nivel a la vez desde la raíz, recordando la profundidad de cada nodo, y comprueba en cada nodo si es una hoja.
Ejecuta una búsqueda en anchura con una cola de pares de nodo y profundidad. El primer nodo que saques que no tenga hijo izquierdo ni derecho da la respuesta, así que devuelve su profundidad de inmediato. Un nodo con un solo hijo no es una hoja.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(w)
Restricciones
- the tree may be empty
Solución
La búsqueda en anchura (BFS) saca los nodos en orden de profundidad, así que la primera hoja que saca es de profundidad mínima y la búsqueda puede detenerse ahí. Ese corte temprano vale la pena cuando una hoja está cerca de la raíz de un árbol grande, donde un recorrido en profundidad (DFS) igual visitaría todos los nodos. El error típico es tomar la menor profundidad de los dos subárboles en un nodo con un solo hijo: el lado faltante reporta 0 y el nodo se trata por error como una hoja. El tiempo es O(n) en el peor caso y el espacio es O(w) para el nivel más ancho que guarda la cola.
from collections import deque
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def min_depth(root):
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, depth = queue.popleft()
if not node.left and not node.right:
return depth # BFS meets the shallowest leaf first
for child in (node.left, node.right):
if child:
queue.append((child, depth + 1))
print(min_depth(T(6, T(2, T(1, T(0))), T(9)))) # -> 2
print(min_depth(T(1, None, T(2, None, T(3))))) # -> 3
print(min_depth(None)) # -> 0¿Lo que te frena es la idea y no el código? Fundamentos de árboles lo explica.