Comprobar si el árbol está balanceado
La misión
Problema
Un índice de búsqueda guarda sus claves en un árbol binario y lo reconstruye cada vez que se desbalancea. Un árbol está balanceado en altura cuando, en cada nodo, las alturas de los subárboles izquierdo y derecho difieren como máximo en 1. Dada la raíz de un árbol binario, devuelve True si está balanceado en altura. El árbol tiene hasta 5000 nodos, así que volver a calcular la altura desde cada nodo es un desperdicio.
Ejemplos
Input: tree = 3, left 9, right 20 (children 15 and 7)
Output: True
Input: tree = 1, left 2 (left child 3 with children 4 and 4, right child 3), right 2
Output: False
Por qué: en la raíz, el lado izquierdo tiene 3 niveles de profundidad y el derecho solo 1
Input: tree = empty
Output: True
Por qué: caso límite: un árbol vacío no tiene nada desbalanceado
Pistas
0 / 3
Llamar a una función de altura desde cada nodo visita los nodos inferiores una y otra vez, lo que es cuadrático en un árbol alto.
Un nodo necesita de todos modos las alturas de sus hijos para comprobarse a sí mismo, y su propia altura es uno más que la mayor de ellas. Un solo recorrido de abajo hacia arriba puede calcular ambas cosas.
Devuelve la altura de cada subárbol desde un recorrido en postorden, o -1 como señal de que algún subárbol de abajo ya está desbalanceado. Pasa el -1 directamente hacia arriba en cuanto lo veas.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(h)
Restricciones
- n ≤ 5000 nodes
Solución
Un único recorrido en postorden devuelve la altura de cada subárbol a su padre, así que cada nodo puede comprobar su propio balance con números que sus hijos ya calcularon. Cuando un nodo encuentra que sus dos alturas difieren en más de uno, devuelve -1 en lugar de una altura, y cada ancestro pasa ese -1 directamente hacia arriba sin hacer más trabajo. El árbol está balanceado exactamente cuando la raíz no devuelve -1. Cada nodo se visita una vez, así que el tiempo es O(n) y el espacio es O(h) para la recursión.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_balanced(root):
def height(node): # height, or -1 if unbalanced below
if node is None:
return 0
lh = height(node.left)
if lh == -1:
return -1
rh = height(node.right)
if rh == -1 or abs(lh - rh) > 1:
return -1
return 1 + max(lh, rh)
return height(root) != -1
print(is_balanced(T(3, T(9), T(20, T(15), T(7))))) # -> True
print(is_balanced(T(1, T(2, T(3, T(4), T(4)), T(3)), T(2)))) # -> False
print(is_balanced(None)) # -> True¿Lo que te frena es la idea y no el código? Profundidad y balance de un árbol lo explica.