Kth Smallest Element in a BST
Recibes un árbol binario de búsqueda como el arreglo root en orden de heap: 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 una posición vacía. El arreglo puede terminar con entradas -1 adicionales. En cada nodo, el subárbol izquierdo contiene solo valores menores y el derecho, solo valores mayores.
Devuelve el valor más pequeño número k del árbol, contando desde 1.
Función
- rootinteger-array
- el árbol binario de búsqueda en orden por niveles, con -1 para una posición vacía
- kinteger
- la posición que se debe encontrar en orden creciente, empezando por 1
- Devuelveinteger
- el k-ésimo valor más pequeño del árbol
Restricciones
1 ≤ root.length ≤ 32767- Cada
root[i]es-1o un valor con0 ≤ root[i] ≤ 105. root[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. - La regla de orden se cumple en cada nodo, por lo que ningún valor aparece dos veces.
1 ≤ k ≤el número de nodos del árbol.
Ejemplos
- Entrada
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Salida
- 29
- Explicación
- En orden creciente, los valores son
6, 17, 22, 29, 41, 65, 90, y el cuarto es29. Es el mayor de los cuatro valores del subárbol izquierdo de la raíz.
- Entrada
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Salida
- 2
- Explicación
- El valor más pequeño termina el camino que sigue hacia la izquierda:
12,5,2. El7debajo de9y el relleno-1no cambian eso.
Para ir más allá
Si el árbol cambia con frecuencia y te piden muchas veces el valor que ocupa la posición k en orden ascendente, ¿qué podría almacenar cada nodo para que cada consulta tarde O(h)?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
¿Qué forma de recorrer un árbol de búsqueda binaria enumera sus valores de menor a mayor?
Recorrer el subárbol izquierdo, después el nodo y después el subárbol derecho da el orden ordenado. El valor número
kque produce ese recorrido es la respuesta, así que puedes detenerte ahí.Usa una pila. Desde el nodo actual, apila nodos mientras avanzas al hijo izquierdo. Desapila el elemento superior y cuéntalo; detente en la
k-ésima extracción. De lo contrario, avanza al hijo derecho del nodo extraído, en2*i+2, y repite.
Solución
Un recorrido en orden (subárbol izquierdo, nodo, subárbol derecho) lee los valores de un árbol de búsqueda binaria en orden creciente, así que el valor número k al que llega es la respuesta. Ejecuta el recorrido con tu propia pila y detente ahí; no hace falta ordenar.
Recopila todos los valores y ordénalos
Intuición
Ignora la estructura: conserva todas las entradas que no sean -1, ordénalas y devuelve la posición k-1. Para el primer ejemplo, la lista ordenada es 6, 17, 22, 29, 41, 65, 90, y en la posición 3 está 29.
Es correcto para cualquier árbol, ordenado o no. Ese es también su coste: ignora el orden que ya tiene el árbol y paga O(n log n) por la ordenación y O(n) de memoria para la copia.
Algoritmo
- Recopila cada elemento de
rootque no sea-1. - Ordena los valores recopilados en orden creciente.
- Devuelve el valor en la posición
k-1.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]Recorrido en orden hacia una lista
Intuición
Debajo de cualquier nodo, el subárbol izquierdo contiene solo valores menores y el derecho, solo valores mayores. Recorre el subárbol izquierdo, después el nodo y después el derecho, y haz lo mismo dentro de cada subárbol: cada nodo queda después de todos los valores menores y antes de todos los mayores, así que la salida queda ordenada. En el primer ejemplo, el recorrido produce 6, 17, 22, 29, 41, 65, 90.
Una pasada reemplaza la ordenación: tiempo O(n) y espacio O(n) para la lista. Aun así, recorre todo el árbol, incluso para k = 1, cuando la respuesta está al final de la ruta más a la izquierda.
Algoritmo
- Escribe
inorder(i): devuelve el control cuando se llegue a una posición vacía (más allá del final o-1). - De lo contrario, llama a
inorder(2*i+1), añaderoot[i]a la lista y después llama ainorder(2*i+2). - Llama a
inorder(0). - Devuelve la entrada de la lista en la posición
k-1.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedRecorrido iterativo en orden que se detiene en k
Intuición
Una pila explícita te permite detener el recorrido a mitad de camino. Ve hacia la izquierda todo lo que puedas, apilando cada nodo. El nodo de arriba es el valor más pequeño que aún no se ha contado, porque todo lo menor está en su subárbol izquierdo, que está vacío o ya se ha contado. Desapílalo y cuéntalo; su subárbol derecho es el siguiente en el orden ascendente.
Para k = 4 en el primer ejemplo: apila 41, 17, 6. Desapila 6, luego 17, y pasa a su hijo derecho: apila 29 y 22. Desapila 22, luego 29, el cuarto. El recorrido nunca toca 65 ni 90.
La pila contiene como máximo un nodo por nivel, así que el espacio es O(h). El recorrido baja una vez y luego desapila k veces: tiempo O(h + k).
Algoritmo
- Empieza con una pila vacía y
i = 0. - Mientras
isea un nodo real, apílalo y avanza a2*i+1. - Desapila el elemento superior y asígnalo a
i, y resta1ak. - Si ahora
kes0, devuelveroot[i]. - De lo contrario, avanza a
2*i+2y vuelve al paso 2.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
Errores comunes y casos límite
- Leer el arreglo en orden de índices. El recorrido por niveles no está ordenado: el primer ejemplo empieza con
41, 17, 65. - Un error de una posición en
k. Cuenta desde1: devuelve la posiciónk-1de la lista y detén el recorrido cuando el conteo llegue ak. - Omitir el subárbol derecho después de extraer un elemento. En el segundo ejemplo,
9y7están en el subárbol derecho de5, y el recorrido nunca los contaría. - Tratar un hijo inexistente como real. Un hijo está vacío cuando su índice supera el final o contiene
-1:22está en el índice9, así que sus hijos19y20están más allá del final. - Los arreglos de Lua y R empiezan en 1. Mantén los índices de los nodos basados en 0 para
2*i+1y leeroot[i + 1].
Preguntas frecuentes3
¿Cuál es la complejidad temporal de encontrar el k-ésimo elemento más pequeño en un BST?
El recorrido iterativo en orden tarda O(h + k) y requiere O(h) de espacio adicional para un árbol de profundidad h. En el peor caso, k = n o si el árbol tiene forma de camino, es decir, O(n).
¿Cómo encuentras el k-ésimo elemento más grande en un BST?
Refleja el recorrido: subárbol derecho, después el nodo y después el subárbol izquierdo. Así se enumeran los valores en orden decreciente. Ve hacia la derecha todo lo que puedas mientras apilas, desapila y cuenta, y pasa al hijo izquierdo después de cada desapilado. El k-ésimo desapilado es el k-ésimo mayor.
¿Cómo detienes un recorrido recursivo en orden en el valor k-ésimo?
Mantén un contador fuera de la recursión, comenzando en k. Réstale 1 cuando regrese el subárbol izquierdo de un nodo y registra el valor del nodo cuando el contador llegue a 0. Después de cada llamada, retorna de inmediato si la respuesta ya está registrada. Así, la recursión iguala la versión con pila: tiempo O(h + k), espacio O(h).
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def kthSmallest(root, k):
# Escribe el código aquíPrueba #1
Prueba #2
Argumentos
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Salida Esperada
29