Invirtiendo un Árbol binario

Últimamente he estado resolviendo muchos problemas en LeetCode, la mayoría relacionados con recursión.

Gracias a eso, finalmente llegué a comprender los árboles binarios, y aunque al principio solía tener muchas dificultades, ahora la mayoría de los problemas me parecen un poco triviales.

El código

Sin más preámbulos, aquí está mi solución:

  var invertTree = function (root) {
    function invert(node) {
        if (node === null) {
            return;
        }
        let temp = node.left;
        node.left = node.right;
        node.right = temp;
        invert(node.left);
        invert(node.right);
    }
    invert(root);
    return root;
};

Elegante y sencillo, ¿verdad? Ahora expliquemos qué está sucediendo:

Sabemos que cada árbol puede tener

• un hijo izquierdo,
• un hijo derecho,
• o ambos.

Para invertir un árbol binario, queremos intercambiar los hijos izquierdo y derecho de cada nodo en todo el árbol.

Así es como funciona el código paso a paso:

1. Caso base: Si el nodo actual es “null”, simplemente retornamos “null”. Esto detiene la recursión cuando llegamos a las hojas.

2. Intercambiar hijos: Para el nodo actual, intercambiamos sus hijos izquierdo y derecho.

3. Llamadas recursivas: Invertimos recursivamente los subárboles izquierdo y derecho (que acaban de ser intercambiados).

Este proceso continúa hasta que cada nodo del árbol ha intercambiado sus hijos, resultando en un árbol binario completamente invertido (espejado).

Este enfoque utiliza recursión, que es una solución natural para problemas con árboles porque cada subárbol es en sí mismo un árbol.

  var invertTree = function (root) {
    function invert(node) { 
        if (node === null) { // Primero siempre verificamos si el nodo es null
            return; // Aquí termina el juego, si el nodo es null entonces no hay nada más que hacer, retornamos.
        }
        let temp = node.left; // Necesitamos crear una copia temporal de uno de los nodos.
        node.left = node.right; // Intercambiamos el izquierdo por el derecho
        node.right = temp; // Intercambiamos el derecho por el temporal
        invert(node.left); // Repetimos el proceso con el izquierdo...
        invert(node.right); // Y con el derecho
    }
    invert(root);
    return root;
};

Conclusión

Este metodo es conciso y eficiente, haciendolo una solución perfecta para el problema.