Descripción del desafío
El problema consiste en transformar una lista enlazada simple, cuyos elementos están ordenados de forma ascendente, en un árbol binario de búsqueda (BST) que esté balanceado en altura. Un árbol balanceado se define como aquel en el que la diferencia de profundidad entre los subárboles izquierdo y derecho de cualquier nodo nunca es superior a uno.
Enfoque 1: Transformación intermedia a estructura lineal
La técnica más directa consiste en convertir la lista enlazada en un arreglo dinámico. Una vez que los datos están en un formato de acceso aleatorio, el problema se reduce a construir un BST a partir de un arreglo ordenado, seleccionando siempre el elemento central como raíz para garantizar el equilibrio.
Análisis de complejidad
- Tiempo: O(N), debido a que recorremos la lista una vez para crear el arreglo y luego visitamos cada elemento para construir el árbol.
- Espacio: O(N), ya que necesitamos almacenar todos los valores de la lista en una estructura de datos adicional.
Implementación en Python
class Solucion:
def construir_bst_desde_arreglo(self, valores):
if not valores:
return None
# Seleccionamos el punto medio para mantener el balance
indice_medio = len(valores) // 2
nodo_raiz = TreeNode(valores[indice_medio])
# Construcción recursiva de subárboles
nodo_raiz.left = self.construir_bst_desde_arreglo(valores[:indice_medio])
nodo_raiz.right = self.construir_bst_desde_arreglo(valores[indice_medio + 1:])
return nodo_raiz
def sortedListToBST(self, inicio_lista):
# Conversión de lista enlazada a lista de Python
elementos = []
puntero = inicio_lista
while puntero:
elementos.append(puntero.val)
puntero = puntero.next
return self.construir_bst_desde_arreglo(elementos)
Enfoque 2: Construcción optimizada con recorrido en inorden
Es posible optimizar el uso del espacio aprovechando la naturaleza del recorrido en inorden (izquierda -> raíz -> derecha). Dado que la lista enlazada ya está ordenada, coincide exactamente con el orden en que los nodos de un BST son visitados durante un recorrido en inorden.
El proceso sigue estos pasos:
- Contar el número total de nodos en la lista.
- Utilizar la cuenta para definir los límites de los subárboles izquierdo y derecho de forma recursiav.
- Construri el subárbol izquierdo, asignar el valor del nodo actual de la lista a la raíz y luego construir el subárbol derecho, avanzando el puntero de la lista en cada paso.
Análisis de complejidad
- Tiempo: O(N), para contar los nodos y realizar la construcción.
- Espacio: O(log N), correspondiente a la profundidad de la pila de recursión (puesto que el árbol es equilibrado).
Implementación en Python
class SolucionOptimizada:
def sortedListToBST(self, head):
# Calcular el tamaño total de la lista
tamanio = 0
temporal = head
while temporal:
tamanio += 1
temporal = temporal.next
self.nodo_actual = head
def generar_arbol(inicio, fin):
if inicio > fin:
return None
mitad = (inicio + fin) // 2
# Primero construimos el lado izquierdo
hijo_izquierdo = generar_arbol(inicio, mitad - 1)
# Procesamos el nodo raíz actual
raiz = TreeNode(self.nodo_actual.val)
raiz.left = hijo_izquierdo
# Avanzamos el puntero de la lista original
self.nodo_actual = self.nodo_actual.next
# Finalmente el lado derecho
raiz.right = generar_arbol(mitad + 1, fin)
return raiz
return generar_arbol(0, tamanio - 1)
Este segundo método es significativamente más eficiente en términos de memoria, ya que evita la creación de una copia completa de los datos y mantiene el balance del árbol dividiendo el rango de nodos de manera equitativa.