Lowest Common Ancestor of a BST

Q: ¿Cuál es la complejidad temporal del ancestro común más bajo en un BST?

El recorrido desde la raíz sigue un solo camino, por lo que tarda O(h) para un árbol de profundidad h y requiere O(1) de espacio adicional. En un árbol equilibrado, eso es O(log n) ; en un árbol con forma de camino único, es O(n) .

Q: ¿En qué se diferencia el LCA en un árbol de búsqueda binaria del LCA en un árbol binario?

En un árbol binario ordinario, un valor puede estar en cualquier lugar, así que buscas en los dos subárboles de cada nodo y el trabajo es O(n) . En un árbol de búsqueda, comparar los dos valores con un nodo te indica en qué lado está cada uno, así que sigues un único camino desde la raíz. El método recursivo para cualquier árbol sigue funcionando en un árbol de búsqueda, pero descarta esa información.

Q: ¿Puede un nodo ser su propio ancestro común más bajo?

Sí. Un nodo cuenta como antepasado de sí mismo, así que cuando p está por encima de q , la respuesta es p . La misma regla da p cuando los dos valores son iguales. El recorrido contempla ambos casos: se detiene en cuanto el nodo actual coincide con uno de los valores.

Q: ¿Por qué se detiene el recorrido en el primer nodo donde p y q se separan?

En ese nodo, un valor es menor y el otro mayor, así que están en subárboles distintos. Cualquier nodo que esté debajo de él se encuentra en solo uno de esos subárboles y no puede contener ambos. El nodo de separación contiene ambos, y ningún nodo más profundo lo hace, lo cual es exactamente la definición del ancestro común más bajo.

MedioÁrbol binario de búsqueda

+10

Se te da un árbol binario de búsqueda almacenado en el arreglo tree en orden por niveles, y dos valores p y q que aparecen en él. 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 arreglo puede terminar con entradas -1 adicionales. En un árbol binario de búsqueda, todos los valores del subárbol izquierdo de un nodo son menores que el valor del nodo, y todos los valores de su subárbol derecho son mayores.

Escribe una función llamada lowestCommonAncestor que devuelva el valor del ancestro común más bajo de p y q: el nodo más profundo que tiene a ambos en su subárbol. Un nodo cuenta como parte de su propio subárbol, así que si p está por encima de q, la respuesta es el propio p.

Función

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

treeinteger-array: el árbol binario de búsqueda en orden por niveles, con -1 para una posición vacía
pinteger: el primer valor que se debe encontrar
qinteger: el segundo valor que se debe encontrar
Devuelveinteger: el valor del nodo más profundo que tiene tanto a p como a q en su subárbol

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.
El arreglo puede terminar con entradas adicionales -1 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.
El árbol es un árbol binario de búsqueda válido, por lo que todos sus valores son distintos.
p y q son valores de nodos del árbol. Pueden venir en cualquier orden y ser iguales.

Ejemplos

Entrada: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
Salida: 8
Explicación: El 3 es el hijo izquierdo de 8, y el 15 cuelga debajo de 12, a la derecha de 8. Al subir desde cada uno de ellos, el primer nodo al que llegan ambos es 8, así que esa es la respuesta; la raíz 20 también es un antepasado común, pero está más arriba.

Entrada: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Salida: 12
Explicación: El 10 es el hijo izquierdo de 12. Un nodo cuenta como su propio ancestro, así que 12 tiene ambos valores en su subárbol y nada que esté debajo de él los tiene: la respuesta es 12. Los valores pueden aparecer en cualquier orden; aquí p es el mayor.

Entrada: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Salida: 70
Explicación: Tanto 55 como 80 son mayores que la raíz 50, así que ambos están a su derecha. En 70 se separan: 55 es menor y está a la izquierda (debajo de 60), 80 es mayor y está a la derecha. Así que 70 es la respuesta.

+12 pruebas ocultas al enviar

Para ir más allá

¿Qué cambiarías si p o q pudieran no estar en el árbol y la función tuviera que devolver -1 en ese caso?

Pistas

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

0 de 3 abiertas

Solución

En un árbol binario común, no puedes saber dónde se encuentra un valor sin buscar en ambos lados de cada nodo. Un árbol de búsqueda te indica en cada nodo: los valores menores están a la izquierda y los mayores, a la derecha. Así que empieza en la raíz y avanza hacia el lado que contiene ambos valores. El primer nodo en el que dejan de estar en el mismo lado es la respuesta, y lo encuentras siguiendo un único camino, sin mirar nunca el resto del árbol.

Busca en todo el árbol, sin tener en cuenta el orden

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 [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15], la raíz 20 tiene 8 y 31 en los índices 1 y 2, y el 12 en el índice 4 tiene 10 y 15 en los índices 9 y 10.

Este primer método funciona con cualquier árbol binario. Una llamada recursiva a find(i) informa qué contiene el subárbol en i. Una posición vacía informa -1. Un nodo que contiene p o q se informa a sí mismo: el otro valor está debajo de él y, después, este es la respuesta; o el otro valor está en otra parte y un nodo más arriba encontrará ambos. De lo contrario, el nodo consulta a ambos hijos. Si ambos lados informan algo, p está a un lado y q al otro, así que este nodo es donde se encuentran. Si solo un lado informa algo, se devuelve ese resultado hacia arriba.

Para p = 3 y q = 15, el 8 recibe el índice 3 de su izquierda y el índice 10 de su derecha, así que se informa a sí mismo. La raíz recibe eso de su izquierda y -1 de su derecha, y devuelve el 8 hacia arriba.

Es correcto, pero puede visitar todos los nodos: tiempo O(n), con O(h) para la recursión. Nunca utiliza el orden de los valores, que es precisamente lo importante de un árbol de búsqueda.

Algoritmo

Escribe find(i). Si la posición en i está vacía (más allá del final o -1), devuelve -1.
Si tree[i] es p o q, devuelve i.
Llama a find con 2*i+1 y 2*i+2. Si ambos encontraron algo, devuelve i.
De lo contrario, devuelve el lado que haya encontrado algo, o -1.
Devuelve tree[find(0)].

def lowestCommonAncestor(tree, p, q):
    n = len(tree)

    def find(i):
        # In the subtree at index i: the index of the answer if both values are
        # inside, the index of the one that is, or -1 when neither is.
        if i >= n or tree[i] == -1:
            return -1
        if tree[i] == p or tree[i] == q:
            return i
        left = find(2 * i + 1)
        right = find(2 * i + 2)
        if left != -1 and right != -1:
            return i  # one value on each side: this node is the answer
        return left if left != -1 else right

    return tree[find(0)]

Compara las dos rutas de búsqueda

Intuición

Ahora usa el orden. Puedes encontrar un valor de la manera en que se busca en un árbol de búsqueda: empieza en la raíz, ve a la izquierda cuando el valor sea menor que el nodo, a la derecha cuando sea mayor y detente cuando lo encuentres. Ese recorrido pasa por todos los ancestros del valor y nada más, porque la ruta desde la raíz hasta un nodo es única.

Anota el recorrido para p y el recorrido para q. Ambos empiezan en la raíz y siguen los mismos nodos hasta que los valores toman caminos distintos. El comienzo compartido es la lista de sus ancestros comunes, así que el último valor compartido es el más bajo. Para 3 y 15, las rutas son 20, 8, 3 y 20, 8, 12, 15: comparten 20, 8, y la respuesta es 8. Para 12 y 10, son 20, 8, 12 y 20, 8, 12, 10, y la respuesta es 12.

Cada recorrido toma un paso por nivel, así que el tiempo es O(h), como máximo 14 pasos aquí, independientemente de cuántos nodos tenga el árbol. Las dos listas ocupan O(h) de espacio.

Algoritmo

Escribe path(target): empieza en el índice 0, registra tree[i], detente cuando sea igual a target; de lo contrario, ve a 2*i+1 si target es menor y a 2*i+2 si es mayor.
Construye la ruta a p y la ruta a q.
Recorre ambas listas desde el principio mientras sus valores coincidan, recordando la última coincidencia.
Devuelve ese último valor compartido.

def lowestCommonAncestor(tree, p, q):
    def path(target):
        # The values met on the way from the root down to target.
        values = []
        i = 0
        while True:
            values.append(tree[i])
            if tree[i] == target:
                return values
            i = 2 * i + 1 if target < tree[i] else 2 * i + 2

    to_p, to_q = path(p), path(q)
    # Both paths start at the root; the answer is the last value they share.
    answer = to_p[0]
    for a, b in zip(to_p, to_q):
        if a != b:
            break
        answer = a
    return answer

Desciende hasta que los valores se separen

Intuición

Los dos caminos coinciden mientras p y q avancen en la misma dirección, así que no hace falta almacenarlos. Recorre ambos a la vez. En un nodo que contiene v, si ambos valores son menores que v, ambos están en el subárbol izquierdo, y lo mismo ocurre con cualquier ancestro común debajo de v: ve a la izquierda. Si ambos son mayores, ve a la derecha.

De lo contrario, has llegado. O bien un valor es menor que v y el otro es mayor, así que están en subárboles distintos y ningún hijo de v contiene a ambos; o bien uno de ellos es igual a v, y un nodo es su propio ancestro. En cualquier caso, v es el nodo más profundo que está por encima de ambos.

En el tercer ejemplo, la raíz 50 es menor que 55 y 80, así que ve a la derecha hasta 70. Allí, 55 es menor y 80 es mayor: la respuesta es 70. En el segundo ejemplo, vas de 20 a 8 y luego a 12, que es igual a p, y te detienes.

Sigues un único camino desde la raíz, con un par de comparaciones por nivel, así que el tiempo es O(h) y el espacio es O(1). El resto del árbol nunca se lee.

Algoritmo

Empieza en el índice i = 0.
Lee v = tree[i].
Si p < v y q < v, ve a 2*i+1 y repite.
Si p > v y q > v, ve a 2*i+2 y repite.
De lo contrario, devuelve v.

def lowestCommonAncestor(tree, p, q):
    i = 0  # start at the root
    while True:
        value = tree[i]
        if p < value and q < value:
            i = 2 * i + 1  # both are smaller: the answer is on the left
        elif p > value and q > value:
            i = 2 * i + 2  # both are larger: the answer is on the right
        else:
            return value  # they split here, or one of them is this node

Errores comunes y casos límite

El recorrido es corto, así que la mayoría de los errores se deben a su condición de parada.

Usar ≤ y ≥ en las pruebas de movimiento. Con p = 12 y q = 10, la prueba p ≤ 12 y q ≤ 12 pasa de largo la respuesta hasta 10, y desde ahí el recorrido devuelve 10 o se sale del árbol. Muévete solo cuando ambos valores estén estrictamente en el mismo lado.
Suponer que p < q. Los valores pueden aparecer en cualquier orden. Compara ambos con el nodo o intercámbialos primero para que p sea el menor.
Olvidar que uno de los valores puede ser ancestro del otro. En ese caso, la respuesta es ese mismo valor, no su padre.
Devolver el índice en lugar del valor. La función devuelve tree[i], no i.
Buscar en todo el árbol. Da la respuesta correcta, pero visita todos los nodos, cuando basta con un solo recorrido.
Confundir el desplazamiento en Lua y R, donde los arreglos empiezan en 1. Mantén los índices de los nodos en base 0 para la aritmética 2*i+1 y lee tree[i + 1].

Preguntas frecuentes4

¿Cuál es la complejidad temporal del ancestro común más bajo en un BST?

El recorrido desde la raíz sigue un solo camino, por lo que tarda O(h) para un árbol de profundidad h y requiere O(1) de espacio adicional. En un árbol equilibrado, eso es O(log n); en un árbol con forma de camino único, es O(n).

¿En qué se diferencia el LCA en un árbol de búsqueda binaria del LCA en un árbol binario?

En un árbol binario ordinario, un valor puede estar en cualquier lugar, así que buscas en los dos subárboles de cada nodo y el trabajo es O(n). En un árbol de búsqueda, comparar los dos valores con un nodo te indica en qué lado está cada uno, así que sigues un único camino desde la raíz. El método recursivo para cualquier árbol sigue funcionando en un árbol de búsqueda, pero descarta esa información.

¿Puede un nodo ser su propio ancestro común más bajo?

Sí. Un nodo cuenta como antepasado de sí mismo, así que cuando p está por encima de q, la respuesta es p. La misma regla da p cuando los dos valores son iguales. El recorrido contempla ambos casos: se detiene en cuanto el nodo actual coincide con uno de los valores.

¿Por qué se detiene el recorrido en el primer nodo donde p y q se separan?

En ese nodo, un valor es menor y el otro mayor, así que están en subárboles distintos. Cualquier nodo que esté debajo de él se encuentra en solo uno de esos subárboles y no puede contener ambos. El nodo de separación contiene ambos, y ningún nodo más profundo lo hace, lo cual es exactamente la definición del ancestro común más bajo.

Python

def lowestCommonAncestor(tree, p, q):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

Esperado

Lowest Common Ancestor of a BST

Función

Restricciones

Ejemplos

Pistas

Solución

Busca en todo el árbol, sin tener en cuenta el orden

Compara las dos rutas de búsqueda

Desciende hasta que los valores se separen

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares