Validate Binary Search Tree

Q: ¿Por qué no basta con comprobar cada nodo con respecto a sus hijos para validar un BST?

La regla abarca subárboles completos. Un nodo profundo en el subárbol derecho de la raíz debe ser mayor que la raíz, incluso si es el hijo izquierdo de un nodo mucho mayor. En [10, 5, 15, -1, -1, 6, 20] , el 6 es un hijo izquierdo adecuado de 15 , pero está a la derecha de 10 , así que el árbol no es un árbol de búsqueda. Necesitas los límites de todos los ancestros, no solo del padre.

Q: ¿Cuál es la complejidad temporal de validar un árbol binario de búsqueda?

Ambos métodos estándar, la comprobación en orden y la comprobación de rangos, examinan cada nodo una vez, por lo que tardan O(n) . La comprobación de rangos necesita O(h) de espacio adicional para la pila, donde h es la profundidad. Comparar cada nodo con todos sus subárboles también funciona, pero cuesta O(n × h) , que llega a O(n²) en un árbol con forma de camino.

Q: ¿Puedes validar un BST con un recorrido en orden sin almacenar todos los valores?

Sí. La comprobación en orden solo compara un valor con el que está justo antes, así que guarda el valor anterior en una variable en lugar de en una lista. Recorre el árbol en orden mediante recursión o una pila explícita, y devuelve false en cuanto un valor no sea mayor que el anterior. Así, el espacio adicional se reduce a O(h) .

Q: ¿Puede un árbol de búsqueda binaria contener valores duplicados?

No según la definición estricta que se usa aquí: cada valor de la izquierda debe ser menor y cada valor de la derecha, mayor, así que dos valores iguales nunca pueden encajar ambos. Algunos libros de texto permiten duplicados en un lado, por ejemplo, valores iguales a la derecha. Según esa regla, cambiarías una de las comparaciones estrictas por ≤ , así que lee la definición antes de escribir la comprobación.

MedioÁrbol binario de búsqueda Recorrido de árboles

+10

Recibes un árbol binario almacenado en el array tree en orden por niveles. La raíz está en el índice 0, los hijos del nodo en el índice i están en 2*i+1 (izquierda) y 2*i+2 (derecha), -1 marca una posición vacía y el array puede terminar con entradas -1 adicionales.

Escribe una función llamada isValidBST que devuelva true si el árbol es un árbol de búsqueda binaria y false en caso contrario. En un árbol de búsqueda binaria, 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. Dos valores iguales nunca pueden estar ambos en un árbol válido.

Función

isValidBST(tree: integer-array) → boolean

treeinteger-array: el árbol binario en orden por niveles, con -1 para indicar una posición vacía
Devuelveboolean: verdadero si el árbol es un árbol de búsqueda binaria, falso en caso contrario

Restricciones

1 ≤ tree.length ≤ 32767
Cada tree[i] es -1 o un valor con 0 ≤ tree[i] ≤ 10⁵.
tree[0] nunca es -1, así que el árbol tiene al menos un nodo.
La matriz puede terminar con entradas -1 adicionales 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: Cada nodo está en el lado correcto de cada nodo que tiene encima. Al leer en orden (subárbol izquierdo, nodo, subárbol derecho), los valores son 1, 3, 6, 8, 10, 12, 15, estrictamente crecientes, que es lo que proporciona un árbol de búsqueda.

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, pero el árbol no es válido. El 6 en el índice 5 está en el subárbol derecho de la raíz 10, así que debe ser mayor que 10, y no lo es.

Entrada: tree = [12, 7, 12]
Salida: false
Explicación: El hijo derecho de la raíz contiene 12, el mismo valor que la raíz. El subárbol derecho debe ser estrictamente mayor, así que un valor igual incumple la regla.

+16 pruebas ocultas al enviar

Para ir más allá

El padre del nodo en el índice i se encuentra en (i-1)/2, redondeado hacia abajo. ¿Puedes recorrer el árbol en orden usando un espacio adicional de O(1), avanzando por los padres en lugar de mantener una pila o usar recursión?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La regla se aplica a subárboles completos, no a un nodo y sus dos hijos. Un árbol puede superar la prueba del padre y los hijos en cada nodo y aun así ser incorrecto, porque un nodo situado en lo más profundo puede romper un límite establecido por un antepasado varios niveles más arriba. Dos ideas permiten resolverlo fácilmente: recorrer el árbol en orden y comprobar que los valores aumentan estrictamente, o pasar a cada nodo el rango de valores que permiten sus antepasados y comprobar que se ajusta a ese rango.

Compara cada nodo con sus subárboles completos

Intuición

Primero, cómo desplazarse por el arreglo. El nodo en el índice i tiene su hijo izquierdo en 2*i+1 y su hijo derecho en 2*i+2. Un hijo existe solo si su índice está dentro del arreglo y el valor allí no es -1. En [10, 5, 15, -1, -1, 6, 20], la raíz 10 tiene 5 y 15 en los índices 1 y 2, y el 15 tiene 6 y 20 en los índices 5 y 6.

La primera idea que prueba la mayoría de la gente compara cada nodo solo con sus dos hijos. Ese árbol es la razón por la que falla: 5 < 10, 15 > 10, 6 < 15 y 20 > 15 se cumplen, pero el 6 está a la derecha de 10. La definición habla de todos los valores de un subárbol, así que comprueba exactamente eso.

Para un nodo que contiene v, todo lo que está a su izquierda es menor que v exactamente cuando el valor más grande de la izquierda es menor que v. De la misma manera, todo lo que está a su derecha es mayor que v cuando el valor más pequeño allí es mayor que v. Dos pequeñas funciones auxiliares recursivas encuentran ese valor más grande y ese valor más pequeño. Para un lado vacío, el valor más grande es -1 y el más pequeño es 100001, valores fuera del rango permitido, por lo que un lado vacío nunca falla.

Esto es correcto, pero repite trabajo. Se recorre un nodo una vez por cada antecesor que tiene, así que el total es de aproximadamente n × h visitas para un árbol de profundidad h. Con una profundidad de como máximo 14, aquí está bien, pero en un árbol que sea un único camino largo de n nodos, aumenta hasta O(n²).

Algoritmo

Recorre todos los índices i cuyo valor no sea -1.
Encuentra el valor más grande del subárbol izquierdo que comienza en 2*i+1, o -1 si esa posición está vacía.
Encuentra el valor más pequeño del subárbol derecho que comienza en 2*i+2, o 100001 si esa posición está vacía.
Si el valor más grande es mayor o igual que tree[i], o el más pequeño es menor o igual que tree[i], devuelve false.
Después del último nodo, 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 True

Los valores en orden 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. En un árbol de búsqueda binaria, ese orden está ordenado: todo lo que está a la izquierda es menor, así que va primero, y todo lo que está a la derecha es mayor, así que va después. El primer ejemplo se lee 1, 3, 6, 8, 10, 12, 15.

Lo inverso también se cumple, y eso es lo que hace que esto sea una prueba. Toma cualquier nodo v. En la secuencia en orden, todo su subárbol izquierdo queda justo antes de él 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 lo mismo ocurre con todos los demás nodos.

Así que recorre el árbol en orden, reúne los valores y compara cada uno con el anterior. El segundo ejemplo se lee 5, 10, 6, 15, 20: el paso de 10 a 6 deja al descubierto el nodo que está en el lado equivocado. El tercero se lee 7, 12, 12, y el 12 repetido no supera la comprobación estricta. Cada nodo se visita una vez: tiempo O(n), y la lista ocupa espacio O(n).

Algoritmo

Escribe walk(i): si el lugar está vacío, detente; de lo contrario, recorre 2*i+1, agrega tree[i] y después recorre 2*i+2.
Llama a walk(0) para recopilar los valores en orden.
Para cada posición k a partir de 1, si values[k-1] ≥ values[k], devuelve false.
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 True

Transmite el rango permitido hacia abajo por el árbol

Intuición

Considera la regla desde el punto de vista de un nodo. Cada antecesor impone un límite. Si el nodo está en el subárbol izquierdo de un antecesor con valor a, su valor debe ser menor que a; si está en el subárbol derecho, debe ser mayor que a. Todos esos límites juntos forman un intervalo abierto (low, high), y el nodo está en el lugar correcto exactamente cuando su valor queda estrictamente dentro de ese intervalo.

Puedes construir ese intervalo mientras bajas. La raíz no tiene límites. Al pasar de un nodo con valor v a su hijo izquierdo, se conserva low y se reduce high a v; al pasar a su hijo derecho, se conserva high y se aumenta low a v. El nuevo límite siempre es más estricto que el que reemplaza, porque v superó la comprobación con el intervalo anterior.

En el segundo ejemplo, 15 recibe el intervalo (10, no limit) y se lo pasa a su hijo izquierdo como (10, 15). El 6 es menor que 10, así que la comprobación falla ahí mismo, sin revisar ningún otro nodo. Los valores están entre 0 y 10^5, así que -1 y 100001 sirven como «sin límite».

Mantén los nodos pendientes en una pila, cada uno con su intervalo. Cada nodo se comprueba una vez, en tiempo O(n), y la pila contiene los nodos pendientes de un mismo camino, con espacio O(h). El primer intervalo que no se cumpla pone fin a la búsqueda.

Algoritmo

Agrega (0, -1, 100001): el índice de la raíz y un intervalo abierto sin límites reales.
Extrae (i, low, high). Si tree[i] no está estrictamente entre low y high, devuelve false.
Si el hijo izquierdo 2*i+1 es real, agrégalo con el intervalo (low, tree[i]).
Si el hijo derecho 2*i+2 es real, agrégalo con el intervalo (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

La mayoría de las respuestas incorrectas comprueban demasiado poco o comprueban lo correcto con la comparación equivocada.

Comparar un nodo solo con sus hijos. En [10, 5, 15, -1, -1, 6, 20], todos los pares de padre e hijo parecen correctos, y el 6 sigue infringiendo el límite establecido por la raíz dos niveles más arriba.
Permitir valores iguales. El orden es estricto en ambos lados, así que [12, 7, 12] no es válido. Usa low < v < high y values[k-1] < values[k], nunca ≤.
Pasar únicamente el valor del padre hacia abajo. Un hijo izquierdo necesita ambos límites: estar por debajo de su padre y por encima de cualquier límite inferior que tuviera el padre. Conserva el rango completo.
Elegir un valor «sin límite» que un nodo pueda contener. Los valores empiezan en 0, así que un límite inferior de 0 rechazaría un nodo válido que contenga 0, como en [0]. Empieza por debajo de todos los valores permitidos.
Leer más allá del final del arreglo. Comprueba 2*i+1 < tree.length antes de leer un hijo y considera -1 como la ausencia de un hijo.
Confundir el desplazamiento en Lua y R, donde los arreglos empiezan en 1. Mantén los índices de los nodos basados en 0 para la aritmética de 2*i+1 y lee tree[i + 1].

Preguntas frecuentes4

¿Por qué no basta con comprobar cada nodo con respecto a sus hijos para validar un BST?

La regla abarca subárboles completos. Un nodo profundo en el subárbol derecho de la raíz debe ser mayor que la raíz, incluso si es el hijo izquierdo de un nodo mucho mayor. En [10, 5, 15, -1, -1, 6, 20], el 6 es un hijo izquierdo adecuado de 15, pero está a la derecha de 10, así que el árbol no es un árbol de búsqueda. Necesitas los límites de todos los ancestros, no solo del padre.

¿Cuál es la complejidad temporal de validar un árbol binario de búsqueda?

Ambos métodos estándar, la comprobación en orden y la comprobación de rangos, examinan cada nodo una vez, por lo que tardan O(n). La comprobación de rangos necesita O(h) de espacio adicional para la pila, donde h es la profundidad. Comparar cada nodo con todos sus subárboles también funciona, pero 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 todos los valores?

Sí. La comprobación en orden solo compara un valor con el que está justo antes, así que guarda el valor anterior en una variable en lugar de en una lista. Recorre el árbol en orden mediante recursión o una pila explícita, y devuelve false en cuanto un valor no sea mayor que el anterior. Así, el espacio adicional se reduce a O(h).

¿Puede un árbol de búsqueda binaria contener valores duplicados?

No según la definición estricta que se usa aquí: cada valor de la izquierda debe ser menor y cada valor de la derecha, mayor, así que dos valores iguales nunca pueden encajar ambos. Algunos libros de texto permiten duplicados en un lado, por ejemplo, valores iguales a la derecha. Según esa regla, cambiarías una de las comparaciones estrictas por ≤, así que lee la definición antes de escribir la comprobación.

Python

def isValidBST(tree):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

tree = [8, 3, 12, 1, 6, 10, 15]

Esperado

true

Validate Binary Search Tree

Función

Restricciones

Ejemplos

Pistas

Solución

Compara cada nodo con sus subárboles completos

Los valores en orden deben aumentar estrictamente

Transmite el rango permitido hacia abajo por el árbol

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares