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, así que tarda O(h) para un árbol de profundidad h y usa O(1) espacio adicional. En un árbol equilibrado, eso es O(log n); en un árbol con forma de un único camino, 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 común, un valor puede estar en cualquier lugar, así que puedes buscar en todos los nodos, con un trabajo de O(n). En un árbol de búsqueda, comparar los dos valores con un nodo te indica en qué lado se encuentra cada uno, así que sigues un único camino desde la raíz.

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

Sí. Un nodo cuenta como ancestro de sí mismo, así que cuando p está por encima de q , la respuesta es p , y cuando los dos valores son iguales, la respuesta es ese valor.

MedioÁrbol binario de búsqueda

+10

Se te proporciona un árbol binario de búsqueda almacenado en orden de montón en el arreglo tree: 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), y -1 marca un espacio vacío. Cada valor en el subárbol izquierdo de un nodo es menor que el valor del nodo, y cada valor en su subárbol derecho es mayor.

Escribe lowestCommonAncestor, que devuelve el valor del ancestro común más bajo de los valores p y q, que están ambos en el árbol: el nodo más profundo que tiene a ambos en su subárbol. Un nodo forma parte de su propio subárbol, así que si p está por encima de q, la respuesta es p.

Función

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

treeinteger-array: el árbol de búsqueda binaria en orden por niveles, con -1 para un espacio vacío
pinteger: el primer valor que se debe encontrar
qinteger: el segundo valor que hay que 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 -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.
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 aparecer 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: Al subir desde 3 y desde 15, el primer nodo al que llegan ambos es 8: 3 es su hijo izquierdo y 15 cuelga debajo de 12, a su derecha. La raíz 20 también es un ancestro 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: 10 es el hijo izquierdo de 12, y un nodo cuenta como su propio ancestro, así que 12 contiene ambos valores y ningún nodo por debajo de él los contiene. Aquí p es el valor mayor.

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

Para ir más allá

¿Qué cambiarías si p o q pudieran faltar 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

Un árbol de búsqueda te indica en cada nodo dónde se encuentra un valor: los menores a la izquierda y los mayores a la derecha. Empieza en la raíz y avanza hacia el lado que contiene ambos valores. El primer nodo en el que dejan de compartir un lado es la respuesta, y llegas a él por un solo camino.

Busca todo el árbol, ignorando el orden

Intuición

Este método funciona en cualquier árbol binario. Una llamada recursiva a find(i) informa de qué contiene el subárbol en i. Un nodo que contiene p o q se informa a sí mismo: si el otro valor está debajo, es la respuesta; si no, un nodo más arriba ve ambos. Cualquier otro nodo consulta a sus dos hijos. Si ambos informan de algo, p y q están en lados distintos y este nodo es donde se encuentran; si solo uno informa de algo, se propaga ese resultado hacia arriba.

Para 3 y 15, el 8 recibe el índice 3 de su izquierda y el índice 10 de su derecha, y se informa a sí mismo. Puede visitar todos los nodos: tiempo O(n) y O(h) para la recursión.

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

Busca un valor de la forma habitual: desde la raíz, ve a la izquierda si es menor que el nodo y a la derecha si es mayor. La ruta desde la raíz hasta un nodo es única, así que el recorrido pasa por todos los ancestros del valor y por ningún otro nodo.

Registra ambos recorridos. Comparten nodos hasta que los valores toman caminos distintos, así que el comienzo compartido enumera los ancestros comunes y su último valor es el más bajo. Para 3 y 15, las rutas son 20, 8, 3 y 20, 8, 12, 15: comparten 20, 8, así que la respuesta es 8. Cada recorrido da un paso por nivel: tiempo O(h) y espacio O(h) para las listas.

Algoritmo

Escribe path(target): empieza en el índice 0, registra tree[i], detente cuando sea igual a target; de lo contrario, avanza a 2*i+1 si target es menor y a 2*i+2 si es mayor.
Construye el camino hasta p y el camino hasta q.
Recorre ambas listas desde el principio y devuelve el último valor que tengan en común.

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

Baja hasta que los valores se separen

Intuición

Los dos caminos coinciden mientras p y q avanzan en la misma dirección, así que recórrelos a la vez. En un nodo que contiene v, si ambos valores son menores, los dos están en el subárbol izquierdo, y también lo está todo ancestro común por debajo de v: ve a la izquierda. Si ambos son mayores, ve a la derecha.

De lo contrario, un valor es menor y el otro mayor, así que ningún hijo de v contiene ambos, o uno de ellos es igual a v, que es su propio ancestro. En cualquier caso, v es el nodo más profundo que está por encima de ambos. En el tercer ejemplo, 50 está por debajo de ambos valores, así que ve a la derecha hasta 70, donde 55 es menor y 80 mayor. Un par de comparaciones por nivel da un tiempo O(h) y un espacio O(1).

Algoritmo

Empieza en el índice i = 0.
Lee v = tree[i].
Si p < v y q < v, pasa a 2*i+1 y repite.
Si p > v y q > v, pasa 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

Usar ≤ y ≥ en las pruebas de movimiento. Con p = 12 y q = 10, el recorrido pasa de largo 12 y llega a 10; después devuelve 10 o sale del árbol.
Suponer que p < q. En el segundo ejemplo, p es el valor mayor. Compara ambos con el nodo o intercámbialos primero.
Devolver el índice en lugar del valor. La respuesta es tree[i], no i.
En Lua y R, los arreglos empiezan en 1. Mantén los índices de los nodos basados en 0 para la aritmética 2*i+1 y lee tree[i + 1].

Preguntas frecuentes3

¿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, así que tarda O(h) para un árbol de profundidad h y usa O(1) espacio adicional. En un árbol equilibrado, eso es O(log n); en un árbol con forma de un único camino, 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 común, un valor puede estar en cualquier lugar, así que puedes buscar en todos los nodos, con un trabajo de O(n). En un árbol de búsqueda, comparar los dos valores con un nodo te indica en qué lado se encuentra cada uno, así que sigues un único camino desde la raíz.

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

Sí. Un nodo cuenta como ancestro de sí mismo, así que cuando p está por encima de q, la respuesta es p, y cuando los dos valores son iguales, la respuesta es ese valor.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

Lowest Common Ancestor of a BST

Función

Restricciones

Ejemplos

Pistas

Solución

Busca todo el árbol, ignorando el orden

Compara las dos rutas de búsqueda

Baja hasta que los valores se separen

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares