Lowest Common Ancestor of a Binary Tree
Se te proporciona un árbol binario en el arreglo root, en orden de montículo: 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), y -1 indica una posición vacía. Los valores son distintos y no siguen ningún orden.
Devuelve el valor del ancestro común más bajo de p y q, los valores de dos nodos diferentes: el nodo más profundo cuyo subárbol contiene ambos. Un subárbol incluye su nodo superior, así que, si q está debajo de p, la respuesta es p.
Función
- rootinteger-array
- el árbol binario por niveles, con -1 para indicar una posición vacía
- pinteger
- el valor de un nodo
- qinteger
- el valor de otro nodo
- Devuelveinteger
- el valor del nodo más bajo cuyo subárbol contiene tanto p como q
Restricciones
2 ≤ root.length ≤ 32767- Cada
root[i]es-1o un valor con0 ≤ root[i] ≤ 104. root[0]nunca es-1, y el árbol tiene al menos dos nodos.- El arreglo puede terminar con entradas adicionales
-1despué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. - Todos los valores del árbol son distintos y no siguen ningún orden.
pyqson los valores de dos nodos diferentes del árbol, en cualquier orden.
Ejemplos
- Entrada
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
- Salida
- 3
- Explicación
6es el hijo izquierdo de3, y9está debajo de4, a la derecha de3, así que se encuentran en3. Comparar los valores señalaría la raíz8:6es menor y9es mayor.
- Entrada
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
- Salida
- 4
- Explicación
7es el hijo izquierdo de4, y el subárbol de4incluye al propio4, así que la respuesta es4.
- Entrada
- root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
- Salida
- 6
- Explicación
- La raíz
1no tiene hijo izquierdo. Su hijo derecho6tiene3a su izquierda y0a su derecha, así que los valores se encuentran en6.
Para ir más allá
Si p o q pueden faltar, y la respuesta es -1, ¿qué atajo de la pasada única falla y cómo puedes aun así terminar en un recorrido?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Prueba la regla del árbol de búsqueda con el primer ejemplo:
6es menor que la raíz8y9es mayor. ¿Dónde se encuentran realmente? ¿Qué dice eso sobre la comparación de valores en este árbol?Haz que cada subárbol le diga a su padre qué encontró: nada, uno de los dos valores o la respuesta. Un nodo que recibe información sobre un valor de ambos hijos es donde se encuentran
pyq.Escribe un
find(i)recursivo que devuelva-1si el espacio está vacío,icuandoroot[i]seapoq,icuando ambos hijos devuelvan un índice y, en caso contrario, el resultado del hijo que no sea-1. La respuesta esroot[find(0)].
Solución
Ningún orden te indica qué lado contiene un valor, así que tienes que mirar. Un recorrido en postorden permite que cada subárbol informe de lo que encontró, y los valores se encuentran en el primer nodo que recibe información de ambos lados.
Camina hacia abajo, buscando a cada lado
Intuición
Desciende desde la raíz y, en cada nodo, busca p y q en el subárbol izquierdo. Si están ambos allí: ve a la izquierda. Si no está ninguno: ve a la derecha. Si hay uno de cada lado: los valores se separan y este nodo es la respuesta. Un nodo que contiene p o q también es la respuesta, ya que el otro valor debe estar debajo de él. Para 6 y 9, la raíz encuentra ambos a su izquierda, y en 3, el único 6 contiene solo p.
Cada paso hacia abajo busca en un subárbol completo, así que h niveles cuestan O(n·h), y O(n²) en un árbol alto y estrecho sin límite de profundidad. La búsqueda en 8 ya visitó todos los nodos debajo de 3, y el paso en 3 vuelve a visitar algunos.
Algoritmo
- Escribe
contains(i, value):falsepara un espacio vacío (más allá del final o-1),truesiroot[i]es igual avalue; en caso contrario, consulta ambos hijos. - Empieza en
i = 0. Siroot[i]espoq, devuélvelo. - Si el subárbol izquierdo en
2*i+1contiene ambos valores, ve allí. Si no contiene ninguno, ve a2*i+2. - En caso contrario, devuelve
root[i].
def lowestCommonAncestor(root, p, q):
n = len(root)
def contains(i, value):
# Is value somewhere in the subtree at index i?
if i >= n or root[i] == -1:
return False
if root[i] == value:
return True
return contains(2 * i + 1, value) or contains(2 * i + 2, value)
i = 0 # p and q are always inside the subtree at i
while True:
if root[i] == p or root[i] == q:
return root[i] # one value is here, the other is below it
left = 2 * i + 1
p_left = contains(left, p)
q_left = contains(left, q)
if p_left and q_left:
i = left # both on the left
elif not p_left and not q_left:
i = 2 * i + 2 # both on the right
else:
return root[i] # one on each sideUna pasada en postorden
Intuición
Haz que cada subárbol responda una vez, desde abajo hacia arriba. find(i) devuelve el índice de la respuesta si el subárbol en i contiene ambos valores, el índice de p o q si contiene uno, y -1 si no contiene ninguno.
Un nodo que contiene p o q devuelve su propio índice sin mirar más abajo. Si el otro valor está en su subárbol, este nodo es la respuesta; si no, un nodo más arriba recibe información de ambos lados. Cualquier otro nodo consulta a ambos hijos. Dos resultados significan que los valores llegaron desde lados diferentes y se encuentran aquí. Un único resultado se transmite hacia arriba sin cambios, tanto si corresponde a un valor como si es la respuesta final.
En el primer ejemplo, 3 recibe el índice 3 de su izquierda y 10 de su derecha, devuelve su propio índice 1 y la raíz lo transmite hacia arriba. Cada nodo se visita una vez: tiempo O(n), recursión O(h).
Algoritmo
find(i)devuelve-1para un índice posterior al final o un-1.- Un nodo cuyo valor es
poqdevuelveisin buscar más abajo. - Cualquier otro nodo calcula
left = find(2*i+1)yright = find(2*i+2). Si ninguno es-1, devuelvei; de lo contrario, devuelve el que no sea-1, o-1. - Devuelve
root[find(0)].
def lowestCommonAncestor(root, p, q):
n = len(root)
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 root[i] == -1:
return -1
if root[i] == p or root[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 root[find(0)]
Errores comunes y casos límite
- Comparar los valores con el nodo. El árbol no tiene orden: en el primer ejemplo, ese recorrido se detiene en la raíz
8en lugar de3. - Devolver
trueofalseen lugar de un índice. El padre no puede saber si la respuesta final ya está debajo de él. - Leer un hijo sin comprobar la longitud. El
9en el índice10tiene los índices de hijo21y22, que están más allá de la última entrada. - Devolver
find(0), un índice, en lugar deroot[find(0)]. - En Lua y R, los arreglos empiezan en 1: mantén los índices de los nodos basados en 0 y lee
root[i + 1].
Preguntas frecuentes3
¿Cuál es la complejidad temporal del ancestro común más bajo de un árbol binario?
El recorrido en postorden visita cada nodo como máximo una vez: tiempo O(n). La pila de recursión contiene un marco por nivel, por lo que el espacio es O(log n) en un árbol equilibrado y O(n) en un árbol con forma de camino.
¿En qué se diferencia esto del ancestro común más bajo en un árbol de búsqueda binaria?
En un árbol de búsqueda, comparar p y q con un nodo te indica en qué lado está cada uno, así que un camino desde la raíz encuentra la respuesta en O(h). Aquí, una comparación no te dice nada, así que buscas en los subárboles.
¿Puedes encontrar el ancestro común más bajo con punteros al padre?
Sí. En este arreglo, el padre del índice i es (i-1)/2 redondeado hacia abajo. Mueve el mayor de los dos índices a su padre hasta que sean iguales; un índice mayor nunca es ancestro de uno menor. Con nodos enlazados, coloca los ancestros de p en un conjunto y sube desde q hasta el primero que esté en él.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def lowestCommonAncestor(root, p, q):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9] p = 6 q = 9
Salida Esperada
3