Niveles hasta la hoja más profunda
La misión
Problema
Dada la raíz de un árbol binario, devuelve la cantidad de niveles en el camino más largo desde la raíz hasta cualquier hoja. Un árbol con solo la raíz cuenta como un nivel, y un árbol vacío cuenta como cero.
Ejemplos
Input: tree = 3 with children 9 and 20, where 20 has children 15 and 7
Output: 3
Por qué: el camino 3, 20, 15 abarca tres niveles
Input: tree = 1 with a right child 2, whose right child is 3
Output: 3
Por qué: un árbol totalmente desbalanceado igual cuenta cada nivel
Input: tree = empty
Output: 0
Por qué: caso límite: no hay niveles que contar
Pistas
0 / 3
La profundidad de un árbol depende por completo de sus dos subárboles, que a su vez son árboles. Esa autosimilitud es toda la solución.
Define la respuesta de un nodo en función de las respuestas de sus hijos, y elige para el hijo ausente un caso base que haga funcionar la aritmética.
Para un nodo ausente, reporta cero niveles. Para cualquier nodo real, pide a ambos hijos su profundidad, toma la mayor y suma uno por el nivel que ocupa el propio nodo.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(h)
Restricciones
- the tree may be empty
Solución
La profundidad se define de forma recursiva: un nodo ausente aporta cero niveles, y un nodo presente aporta uno más que el más profundo de sus dos subárboles. Esa única regla trata igual a los árboles balanceados y a los desbalanceados, sin ningún caso especial aparte del hijo vacío. Cada nodo se visita exactamente una vez. El tiempo es O(n) y el espacio es O(h) para la pila de llamadas (call stack), donde h es la altura del árbol.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def depth(node):
if node is None: return 0 # an absent branch adds no level
# a node sits exactly one level above its deeper subtree
return 1 + max(depth(node.left), depth(node.right))
print(depth(T(3, T(9), T(20, T(15), T(7))))) # -> 3
print(depth(T(1, None, T(2, None, T(3))))) # -> 3
print(depth(None)) # -> 0¿Lo que te frena es la idea y no el código? Profundidad y balance de un árbol lo explica.