Recientemente, comencé a practicar algunos ejercicios de LeetCode para mejorar mis habilidades de algoritmo/estructura de datos. Puedo decir que la plataforma proporciona un buen entorno para practicar y aprender con otros desarrolladores soluciones en varios lenguajes de programación, discutir, compartir soluciones con otros y practicar desafíos de código solicitados por grandes empresas.

¿Qué es LeetCode?

LeetCode es un sitio web que ayuda a los candidatos a prepararse para entrevistas de codificación. Los usuarios pueden practicar desafíos utilizando los problemas algorítmicos y de codificación de la plataforma, junto con pruebas predefinidas para la solución del candidato. LeetCode se ha convertido en un recurso popular para entrevistas técnicas y concursos de codificación, junto con HackerRank.

Mi rutina resolviendo problemas

Me propuse el objetivo de resolver al menos 3 desafíos por día, y mi forma de pensar en una solución involucra mi iPad, un lápiz para pantallas y la aplicación Freeform. Intento dibujar y pensar en las soluciones, y esto me ayuda mucho en mis envíos de código. Muchos desafíos suenan difíciles a primera vista, pero con unos minutos se piensa y se diseña la solución (recomiendo escribir el proceso de pensamiento). Si no puedo encontrar la solución adecuada en 30 minutos, veo el envío de otros desarrolladores para descubrir dónde están mis errores (a veces un pequeño paso que olvidé en mi código). Incluso si su solución es lo suficientemente buena, le recomiendo que mire los envíos de otros para pensar en otras formas de resolver ese problema (algunas más o menos eficientes).

El problema del árbol binario invertido

Hace unos días me enfrenté al problema de Invertir Árbol Binario en LeetCode, un desafío muy conocido solicitado en algunas entrevistas y un problema que vi mientras tomaba unas clases de Estructuras de Datos/Algoritmos en la universidad. Aunque nunca enfrenté este desafío en una entrevista y nunca tuve que invertir explícitamente un árbol binario en mi trabajo, saber cómo invertir uno me dio más experiencia con DS, árboles y pensamiento algorítmico y practicó algunas técnicas como la recursividad.
Te recomiendo que intentes solucionar este problema antes de leer el resto de este artículo

la solución

El problema de Invertir árbol binario me pedía: "Dada la raíz de un árbol binario, invertir el árbol y devolver su raíz". (en otras palabras, deberíamos "reflejar" el árbol). Utilicé el lenguaje de programación Java para enviar una solución, pero los pasos son los mismos para otros lenguajes (con pequeños cambios de sintaxis). El ejemplo de entrada y el resultado esperado se muestran a continuación:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Vamos a utilizar la técnica de recursividad para llamar recursivamente al método invertTree(), pasando algún lado del árbol como raíz. Entonces, como lo requiere cada recursividad, necesitamos definir una condición de parada donde la pila de recursividad finalizará y devolverá el resultado respectivo de la llamada de recursividad. Después, simplemente invertimos los lados del árbol, asignando a root.left el valor devuelto por la recursión pasando root.right como parámetro, y hacemos lo mismo con root.right asignando el valor del resultado de la recursión root.left. Como estamos modificando el valor original, necesitamos una variable auxiliar para almacenar el resultado original de root.left (probablemente implementaste un código como este en la universidad y lo llamaste método swap().

Al final devolvemos la raíz con los nodos invertidos. Puedes consultar el siguiente código:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        TreeNode aux = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(aux);

        return root;
    }
}

Tenga en cuenta que podrían existir muchas soluciones diferentes para diferentes problemas, y eso es genial. Todo el mundo tiene una forma de pensar y programar, dominio de estructuras de datos, etc. No es necesario seguir exactamente el mismo código para resolver este problema, pero debe prestar atención a la complejidad del algoritmo (puede usar 3 anidados para resolver un problema). , pero esto tiene menos rendimiento que usar 1 para).