Validate Binary Search Tree
Un árbol binario se almacena en el arreglo tree en orden de heap: la raíz está en el índice 0, los hijos del índice i están en 2*i+1 (izquierdo) y 2*i+2 (derecho), -1 marca un espacio vacío y el arreglo puede terminar con entradas -1 adicionales.
Escribe isValidBST, que devuelve true si el árbol es un árbol binario de búsqueda y false en caso contrario. En un árbol binario de búsqueda, el valor de cada nodo es estrictamente mayor que todos los valores de su subárbol izquierdo y estrictamente menor que todos los valores de su subárbol derecho.
Función
- treeinteger-array
- el árbol binario en orden por niveles, con -1 para una posición vacía
- Devuelveboolean
- verdadero si el árbol es un árbol binario de búsqueda; falso en caso contrario
Restricciones
1 ≤ tree.length ≤ 32767- Cada
tree[i]es-1o un valor con0 ≤ tree[i] ≤ 105. tree[0]nunca es-1, así que el árbol tiene al menos un nodo.- El arreglo 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 pueden repetirse.
Ejemplos
- Entrada
- tree = [8, 3, 12, 1, 6, 10, 15]
- Salida
- true
- Explicación
- Si se lee en orden (subárbol izquierdo, nodo, subárbol derecho), los valores son
1, 3, 6, 8, 10, 12, 15. Aumentan estrictamente, así que cada nodo está en el lado correcto de cada antecesor.
- Entrada
- tree = [10, 5, 15, -1, -1, 6, 20]
- Salida
- false
- Explicación
- Cada nodo es mayor que su hijo izquierdo y menor que su hijo derecho; sin embargo, el
6en el índice5está en el subárbol derecho de la raíz, así que debe ser mayor que10.
- Entrada
- tree = [12, 7, 12]
- Salida
- false
- Explicación
- El hijo derecho de la raíz contiene
12, igual que la raíz. El subárbol derecho debe ser estrictamente mayor, así que el árbol no cumple la condición.
Para ir más allá
El padre de un nodo está en el índice (i-1)/2, redondeado hacia abajo. ¿Puedes recorrer el árbol en orden con espacio adicional O(1), avanzando por los padres en lugar de usar una pila o recurrir a la recursión?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
En
[10, 5, 15, -1, -1, 6, 20], cada nodo es mayor que su hijo izquierdo y menor que su hijo derecho. ¿Por qué sigue sin ser un árbol de búsqueda?Cada antecesor establece un límite para un nodo: por debajo si el nodo está a su izquierda, por encima si está a su derecha. Juntos, esos límites forman un intervalo abierto. Ir a la izquierda desde un valor
vreduce el límite superior av; ir a la derecha aumenta el límite inferior av.Mantén una pila de
(index, low, high), empezando por la raíz y con un intervalo más amplio que cualquier valor permitido. Saca una entrada de la pila, falla si el valor no está estrictamente dentro del intervalo y agrega cada hijo real con su intervalo más ajustado.
Solución
La regla abarca subárboles completos, así que comparar cada nodo con sus dos hijos no basta: un nodo situado a gran profundidad puede infringir un límite establecido por un antepasado varios niveles más arriba. Puedes recorrer el árbol en orden y comprobar que los valores aumenten estrictamente, o pasarle a cada nodo el intervalo permitido por sus antepasados.
Compara cada nodo con todos sus subárboles
Intuición
Todos los valores a la izquierda de un nodo son menores que su valor v si y solo si el mayor valor de ese lado es menor que v, y todos los valores a su derecha son mayores que v si y solo si el menor valor de ese lado es mayor que v. Dos funciones auxiliares recursivas los encuentran. Un lado vacío devuelve -1 o 100001, valores fuera del rango, por lo que nunca falla.
Se recorre cada nodo una vez por cada antecesor, aproximadamente n × h visitas para un árbol de profundidad h. Con una profundidad de como máximo 14, eso es barato, pero en un camino de n nodos crece hasta O(n²).
Algoritmo
- Recorre cada índice
icuyo valor no sea-1. - Encuentra el valor más grande del subárbol izquierdo en
2*i+1(-1si está vacío) y el más pequeño del subárbol derecho en2*i+2(100001si está vacío). - Si el valor más grande es al menos
tree[i], o el más pequeño es como máximotree[i], devuelvefalse. - Devuelve
true.
def isValidBST(tree):
n = len(tree)
def largest(i):
# Largest value in the subtree at index i, or -1 when that spot is empty.
if i >= n or tree[i] == -1:
return -1
return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))
def smallest(i):
# Smallest value in the subtree at index i, or 100001 when that spot is empty.
if i >= n or tree[i] == -1:
return 100001
return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))
for i in range(n):
if tree[i] == -1:
continue
# Everything on the left must be smaller, everything on the right larger.
if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
return False
return TrueLos valores en recorrido inorden deben aumentar estrictamente
Intuición
Un recorrido en orden visita el subárbol izquierdo, después el nodo y después el subárbol derecho, así que en un árbol de búsqueda binaria lee los valores en orden ascendente.
También se cumple lo contrario. Para cualquier nodo v, todo su subárbol izquierdo aparece justo antes que él en la secuencia y todo su subárbol derecho, justo después. Si la secuencia aumenta estrictamente, todos los valores anteriores a v son menores y todos los posteriores son mayores, así que la regla se cumple en v y también en todos los demás nodos.
El segundo ejemplo se lee 5, 10, 6, 15, 20: el descenso de 10 a 6 deja al descubierto el nodo mal ubicado. Cada nodo se visita una vez: tiempo O(n) y espacio O(n) para la lista.
Algoritmo
- Escribe
walk(i): si el espacio está vacío, detente; de lo contrario, recorre2*i+1, agregatree[i]y después recorre2*i+2. - Llama a
walk(0)para recopilar los valores en orden. - Para cada posición
ka partir de1, sivalues[k-1] ≥ values[k], devuelvefalse. - Devuelve
true.
def isValidBST(tree):
n = len(tree)
values = []
def walk(i):
# Left subtree, then the node, then the right subtree.
if i >= n or tree[i] == -1:
return
walk(2 * i + 1)
values.append(tree[i])
walk(2 * i + 2)
walk(0)
# A search tree read in order gives strictly increasing values.
for k in range(1, len(values)):
if values[k - 1] >= values[k]:
return False
return TrueLleva el rango permitido hacia abajo por el árbol
Intuición
Cada antecesor impone un límite a un nodo: por debajo de a si el nodo está en el subárbol izquierdo de un antecesor que contiene a, por encima de a si está en el subárbol derecho. En conjunto, los límites forman un intervalo abierto (low, high), y el nodo está en el lugar correcto exactamente cuando su valor se encuentra estrictamente dentro de él.
Construye el intervalo al bajar. Un hijo izquierdo conserva low y recibe high = v; un hijo derecho conserva high y recibe low = v. En el segundo ejemplo, 15 pasa (10, 15) a su hijo izquierdo, y el 6 falla de inmediato. Los valores están entre 0 y 10^5, así que -1 y 100001 sirven como límites inexistentes. Cada nodo se comprueba una vez, en tiempo O(n), con O(h) nodos en la pila.
Algoritmo
- Apila
(0, -1, 100001): la raíz, sin límites reales. - Desapila
(i, low, high). Sitree[i]no está estrictamente entrelowyhigh, devuelvefalse. - Apila cada hijo real: el izquierdo en
2*i+1con(low, tree[i]), el derecho en2*i+2con(tree[i], high). - Cuando la pila esté vacía, devuelve
true.
def isValidBST(tree):
n = len(tree)
# Each entry: a node index and the open range (low, high) its value must fall in.
# -1 and 100001 lie outside every allowed value, so they mean "no limit".
stack = [(0, -1, 100001)]
while stack:
i, low, high = stack.pop()
value = tree[i]
if not (low < value < high):
return False
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append((left, low, value)) # the left side must stay below value
if right < n and tree[right] != -1:
stack.append((right, value, high)) # the right side must stay above value
return True
Errores comunes y casos límite
- Comparar un nodo solo con sus hijos. En
[10, 5, 15, -1, -1, 6, 20], todos los pares de padre e hijo parecen correctos, pero el6infringe el límite de la raíz. - Permitir valores iguales.
[12, 7, 12]no es válido: compara con<, nunca con≤. - Usar
0como límite inferior «sin límite». Esto rechaza el árbol válido[0]. - Leer un hijo sin comprobar
2*i+1 < tree.length. En[12, 7, 12], el índice3está fuera del rango. - En Lua y R, los arreglos comienzan en 1. Mantén los índices de los nodos basados en 0 para
2*i+1y leetree[i + 1].
Preguntas frecuentes3
¿Cuál es la complejidad temporal de validar un árbol binario de búsqueda?
La comprobación en orden y la comprobación de rangos visitan cada nodo una vez: tiempo O(n), con espacio adicional O(h) para la pila de la comprobación de rangos en un árbol de profundidad h. Comparar cada nodo con sus subárboles completos cuesta O(n × h), que llega a O(n²) en un árbol con forma de camino.
¿Puedes validar un BST con un recorrido en orden sin almacenar cada valor?
Sí. La comprobación solo compara cada valor con el anterior, así que guarda el valor anterior en una variable en lugar de una lista y devuelve false en cuanto un valor no sea mayor. El espacio adicional se reduce a O(h) para la recursión o la pila.
¿Puede un árbol de búsqueda binaria contener valores duplicados?
No según la definición estricta que se usa aquí: un valor igual no encaja en ninguno de los dos lados. Algunos libros de texto permiten valores iguales en un lado, por ejemplo, el derecho. Según esa regla, una comparación estricta se convierte en ≤.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def isValidBST(tree):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
tree = [8, 3, 12, 1, 6, 10, 15]
Salida Esperada
true