Balanced Binary Tree
El array root contiene un árbol binario. La raíz está en el índice 0, los hijos del índice i están en 2*i+1 (izquierda) y 2*i+2 (derecha), -1 marca una posición vacía y puede haber entradas adicionales -1 al final.
Devuelve true si el árbol está equilibrado en altura, lo que significa que en cada nodo las alturas de los subárboles izquierdo y derecho difieren como máximo en 1, y false en caso contrario. La altura de un subárbol es el número de nodos en su camino descendente más largo; un subárbol vacío tiene altura 0.
Función
- rootinteger-array
- el árbol binario en orden por niveles, con -1 para una posición vacía
- Devuelveboolean
- true si las alturas de los dos subárboles de cada nodo difieren como máximo en 1, false en caso contrario
Restricciones
1 ≤ root.length ≤ 32767- Cada
root[i]es-1o un valor con0 ≤ root[i] ≤ 105. root[0]nunca es-1, así que el árbol tiene al menos un nodo.- The 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. - Los valores de los nodos son distintos.
Ejemplos
- Entrada
- root = [5, 2, 9, -1, -1, 7, 11]
- Salida
- true
- Explicación
- El subárbol izquierdo de la raíz es el nodo único
2, de altura1. Su subárbol derecho9,7,11tiene altura2. Difieren en1, y todos los demás nodos tienen dos subárboles de la misma altura.
- Entrada
- root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
- Salida
- false
- Explicación
- Ambos lados de la raíz tienen altura
3, pero el nodo3no cumple: su subárbol izquierdo1,0tiene altura2y el derecho está vacío.
- Entrada
- root = [4, 2, -1, 1]
- Salida
- false
- Explicación
- La raíz tiene la cadena
2,1a su izquierda, altura2, y nada a su derecha, altura0. Una diferencia de2es demasiado.
Para ir más allá
¿Puedes recorrer el árbol sin recursión, usando una pila explícita?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Un árbol puede superar la prueba en la raíz y fallar un nivel más abajo. ¿Qué dos números necesitas en un nodo para comprobarlo allí?
Necesitas las alturas de los dos subárboles del nodo. Calcular la altura desde cero en cada nodo recorre los mismos nodos muchas veces. ¿Puede una visita a un nodo darle a su padre tanto su altura como información sobre si todo lo que hay debajo pasó la prueba?
Escribe una función de recorrido en postorden que devuelva la altura de un subárbol, o
-1cuando el subárbol no esté equilibrado. En un nodo, devuelve-1si un hijo devolvió-1o si las dos alturas difieren en más de1; de lo contrario, devuelve1 + max(left, right).
Solución
La regla se aplica en cada nodo, así que un árbol cuya raíz parece equilibrada aún puede fallar más abajo, como ocurre en el segundo ejemplo en 3. Un recorrido en postorden calcula la altura de cada subárbol una sola vez y propaga el fallo en cuanto aparece, en O(n).
Recalcula las alturas en cada nodo
Intuición
Convierte la definición en código. height(i) es 0 en un espacio vacío y 1 más que la altura del hijo más alto en cualquier otro caso. Compara las alturas de los dos hijos en cada nodo real; el primer nodo en el que difieran en más de 1 hace que la respuesta sea false.
Cada comprobación recorre todo el subárbol debajo de su nodo, así que un nodo se recorre una vez por cada nodo que tiene encima: O(n·h). Con un máximo de 14 niveles, un árbol completo de 16,383 nodos cuesta unos 2 × 10^5 pasos. Una cadena de n nodos costaría O(n²).
Algoritmo
- Define
height(i)como0para un índice más allá del final o un-1, y como1 + max(height(2*i+1), height(2*i+2))para un nodo real. - Visita cada índice
ique contenga un nodo real. - Si
height(2*i+1)yheight(2*i+2)difieren en más de1, devuelvefalse. - Si el bucle termina sin fallos, devuelve
true.
def isBalanced(root):
n = len(root)
def height(i):
# The number of nodes on the longest downward path from index i.
if i >= n or root[i] == -1:
return 0
return 1 + max(height(2 * i + 1), height(2 * i + 2))
# Check every real node, measuring both subtrees from scratch.
for i in range(n):
if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
return False
return TrueUn recorrido en postorden que informa la altura o el fallo
Intuición
La comprobación en un nodo necesita las alturas de sus dos subárboles, y esas también son las que el nodo necesita para informar de su propia altura. Así que obtén ambas en una visita en postorden: cada llamada devuelve la altura de su subárbol después de que hayan devuelto ambos hijos.
Un fallo en un nivel inferior también debe propagarse hacia arriba. Una altura real nunca es negativa, así que usa -1 para indicarlo: una llamada devuelve -1 cuando un hijo devolvió -1 o las alturas de los hijos difieren en más de 1. En el segundo ejemplo, el 3 ve las alturas 2 y 0 y devuelve -1, y la raíz lo propaga sin visitar su lado derecho.
No se visita ningún nodo dos veces, así que el tiempo es O(n), con O(h) llamadas en la pila.
Algoritmo
- Escribe
check(i). Si el índice está más allá del final o es-1, devuelve0. - Calcula
left = check(2*i+1). Si es-1, devuelve-1. - Calcula
right = check(2*i+2). Si es-1, o sileftyrightdifieren en más de1, devuelve-1. - De lo contrario, devuelve
1 + max(left, right). - Devuelve si
check(0)no es-1.
def isBalanced(root):
n = len(root)
def check(i):
# The height of the subtree at index i, or -1 if it is not balanced.
if i >= n or root[i] == -1:
return 0
left = check(2 * i + 1)
if left == -1:
return -1
right = check(2 * i + 2)
if right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
return check(0) != -1
Errores comunes y casos límite
- Comprobar solo la raíz. En el segundo ejemplo, ambos lados de la raíz tienen altura
3, pero el nodo3tiene un desequilibrio de2. - Comparar la hoja menos profunda con la más profunda. El árbol equilibrado más pequeño de altura
6tiene hojas en las profundidades4y6, y todos sus nodos pasan la comprobación. - Perder un fallo al ascender. Si un hijo devuelve
-1y el padre calcula1 + max(-1, 2), el fallo vuelve a convertirse en una altura. - Usar la longitud del array como altura. Las entradas
-1finales hacen que el array sea más largo que la profundidad del árbol. - En Lua y R, los arrays empiezan en 1. Mantén los índices de los nodos basados en 0 para
2*i+1y leeroot[i + 1].
Preguntas frecuentes3
¿Cuál es la complejidad temporal de un árbol binario equilibrado?
Un recorrido en postorden visita cada nodo una vez: tiempo O(n) y espacio de pila O(h) para un árbol de altura h. Recalcular las alturas en cada nodo cuesta O(n·h), lo que se convierte en O(n²) en una cadena.
¿Qué significa que un árbol binario esté equilibrado en altura?
En cada nodo, las alturas de los subárboles izquierdo y derecho difieren como máximo en 1. Los árboles AVL restauran esta propiedad después de cada inserción y eliminación, lo que mantiene su altura en O(log n).
¿Un árbol binario completo siempre está equilibrado?
Sí. Todos los niveles de un árbol completo están llenos, excepto posiblemente el último, que se llena desde la izquierda, así que en cualquier nodo las alturas de los dos subárboles difieren como máximo en 1. Lo contrario es falso: un árbol equilibrado puede tener huecos a la izquierda de su último nivel.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def isBalanced(root):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
root = [5, 2, 9, -1, -1, 7, 11]
Salida Esperada
true