[Leetcode] 0230. Késimo elemento más pequeño en un BST

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Dado que raíz de un árbol de búsqueda binario y un entero k, devolver el k ^o valor más pequeño (1-indexado) de todos los valores de los nodos del árbol.

Ejemplo 1:

Aporte: raíz = [3,1,4,nulo,2], k = 1
Producción: 1

Ejemplo 2:

Aporte: raíz = [5,3,6,2,4,nulo,nulo,1], k = 3
Producción: 3

Restricciones:

El número de nodos en el árbol es norte.
1 <= k <= n <= 10 ⁴
0 <= Nodo.val <= 10 ⁴

Hacer un seguimiento: Si la BST se modifica con frecuencia (es decir, podemos realizar operaciones de inserción y eliminación) y necesita encontrar el k-ésimo más pequeño con frecuencia, ¿cómo optimizaría?

Pitón

				
					# Definición de un nodo de árbol binario. de escribir importar Lista, Clase opcional NodoÁrbol: def __init__(self, val=0, izquierda=Ninguno, derecha=Ninguno): self.val = val self.izquierda = izquierda self.derecha = derecha clase Solución: def addToArr(self, nodo: Opcional[NodoÁrbol], ListaÁrbol: Lista[int]) -> Ninguno: si nodo: self.addToArr(nodo.izquierda, ListaÁrbol) ListaÁrbol.append(nodo.val) self.addToArr(nodo.derecha, ListaÁrbol) def kthSmallest(self, raíz: Opcional[NodoÁrbol], k: int) -> int: resultado = [] self.addToArr(raíz, resultado) devolver resultado[k-1]

Medio

Pitón

Artículos relacionados