Leetcode 108 Convert Sorted Array to Binary Search Tree es un ejercicio clásico: dado un arreglo ordenado, conviértelo en un árbol binario de búsqueda equilibrado en altura. Un árbol está equilibrado en altura si la profundidad de los dos subárboles de cada nodo no difiere en más de uno. Este reto es habitual en entrevistas porque combina recursión, pensamiento de búsqueda binaria y construcción de árboles.
Intuición: como el arreglo está ordenado, el elemento central es el mejor candidato para la raíz. Todo lo que queda a la izquierda del centro es menor y forma el subárbol izquierdo, y todo lo que queda a la derecha es mayor y forma el subárbol derecho. Eligiendo siempre el centro y repitiendo el proceso de forma recursiva con las subpartes, el árbol se mantiene lo más equilibrado posible.
Ejemplo rápido: nums = [-10, -3, 0, 5, 9]. Elegimos 0 como raíz. A la izquierda construimos con [-10, -3] y a la derecha con [5, 9]. Repetimos el mismo criterio con cada subarreglo para obtener un ABB equilibrado.
Enfoque paso a paso: 1 define un helper recursivo con dos índices l y r que acotan el subarreglo actual. 2 caso base si l > r, no hay nada que construir y devolvemos null. 3 calcula el índice central con m = Math.floor((l + r) / 2). 4 crea un nodo con nums[m]. 5 construye recursivamente el subárbol izquierdo con helper(l, m - 1) y el derecho con helper(m + 1, r). 6 devuelve el nodo.
Código JavaScript en una línea para integrarlo fácilmente en cualquier base de código: /** Definition for a binary tree node. function TreeNode(val, left, right) { this.val = val===undefined ? 0 : val; this.left = left===undefined ? null : left; this.right = right===undefined ? null : right } @param {number[]} nums @return {TreeNode} */ var sortedArrayToBST = function(nums) { const helper = (l, r) => { if (l > r) return null; let m = Math.floor((l + r) / 2); let node = new TreeNode(nums[m]); node.left = helper(l, m - 1); node.right = helper(m + 1, r); return node; }; return helper(0, nums.length - 1); };
Análisis de complejidad: tiempo O(n) porque cada elemento del arreglo se usa exactamente una vez para crear un nodo. Espacio O(log n) en promedio debido a la profundidad de la pila recursiva en un árbol equilibrado; en el peor caso puede ser O(n) por la recursión.
Ideas clave: 1 arreglo ordenado más elección del elemento medio produce un ABB perfectamente equilibrado. 2 divide y vencerás minimiza la altura del árbol. 3 es un patrón de recursión que refuerza la intuición de búsqueda binaria y diseño de estructuras de datos.
En Q2BSTUDIO impulsamos soluciones inteligentes que convierten la teoría en práctica. Desarrollamos aplicaciones a medida y software a medida optimizados para datos y alto rendimiento, implementamos ia para empresas con agentes IA y modelos especializados, y reforzamos la ciberseguridad de extremo a extremo. Si quieres escalar tu producto con algoritmos eficientes y capacidades de inteligencia artificial, descubre nuestros servicios de inteligencia artificial y nuestro enfoque de desarrollo de software a medida. También trabajamos con servicios cloud aws y azure, servicios inteligencia de negocio y power bi para acelerar tus decisiones con datos fiables.