Saltar al contenido

Comprobar si el árbol está balanceado

Fácil#post-order#early-exit~15 min

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

Tiempo objetivo
O(n)
Espacio objetivo
O(h)

Restricciones

  • n ≤ 5000 nodes

¿Lo que te frena es la idea y no el código? Profundidad y balance de un árbol lo explica.

Python 3Ctrl+Enter ejecuta