513. Valor Más a la Izquierda del Árbol

Utilizando un recorrido por niveles, guardamos el primer valor de cada nivel. Así, cada vez que procesamos un nivel, actualizamos el valor izquierdo, hasta llegar al último nivel.

class Solucion {
public:
    int encontrarValorInferiorIzquierdo(NodoArbol* raiz) {
        cola<NodoArbol*> cola;
        if (raiz != NULL) cola.push(raiz);
        int resultado = 0;
        while (!cola.empty()) {
            int tamanio = cola.size();
            for (int i = 0; i < tamanio; i++) {
                NodoArbol* nodoActual = cola.front();
                cola.pop();
                if (i == 0) resultado = nodoActual->valor; // Almacenar el primer elemento de la última fila
                if (nodoActual->izquierda) cola.push(nodoActual->izquierda);
                if (nodoActual->derecha) cola.push(nodoActual->derecha);
            }
        }
        return resultado;
    }
};

112. Suma de Rutas 113. Suma de Rutas II

1. Empleamos recursión con backtracking para calcular la suma de cada ruta desde el nodo raíz hasta las hojas. En esta implementación, uitlizamos un contador que llega a cero para verificar si se cumple la condición, transformando el resultado de la suma en una resta. Esto nos permite evitar pasar la variable sum como parámetro, simplfiicando el código.

class Solucion {
private:
    bool recorrer(NodoArbol* actual, int contador) {
        if (!actual->izquierda && !actual->derecha && contador == 0) return true; // Encontrado nodo hoja con contador en cero
        if (!actual->izquierda && !actual->derecha) return false; // Nodo hoja sin cumplir condición

        if (actual->izquierda) { // Rama izquierda
            contador -= actual->izquierda->valor; // Procesar nodo;
            if (recorrer(actual->izquierda, contador)) return true;
            contador += actual->izquierda->valor; // Backtracking, deshacer procesamiento
        }
        if (actual->derecha) { // Rama derecha
            contador -= actual->derecha->valor; // Procesar nodo;
            if (recorrer(actual->derecha, contador)) return true;
            contador += actual->derecha->valor; // Backtracking, deshacer procesamiento
        }
        return false;
    }

public:
    bool tieneSumaRuta(NodoArbol* raiz, int suma) {
        if (raiz == NULL) return false;
        return recorrer(raiz, suma - raiz->valor);
    }
};

2. Modificando el código anterior, cambiamos el tipo de retorno a vector. Luego, ajustamos las condiciones booleanas a operaciones adecuadas con vectores.

class Solucion {
private:
    vector<vector<int>> respuestas;
    vector<int> rutaActual;
    void recorrer(NodoArbol* actual, int contador) {
        if (!actual->izquierda && !actual->derecha && contador == 0){
            respuestas.push_back(rutaActual); // Encontrada ruta válida
            return ;
        }
        if (!actual->izquierda && !actual->derecha) return ; // Nodo hoja sin cumplir condición

        if (actual->izquierda) { // Rama izquierda
            rutaActual.push_back(actual->izquierda->valor);
            contador -= actual->izquierda->valor; // Procesar nodo;
            recorrer(actual->izquierda, contador);
            contador += actual->izquierda->valor; // Backtracking
            rutaActual.pop_back();
        }
        if (actual->derecha) { // Rama derecha
            rutaActual.push_back(actual->derecha->valor);
            contador -= actual->derecha->valor; // Procesar nodo;
            recorrer(actual->derecha, contador);
            contador += actual->derecha->valor; // Backtracking
            rutaActual.pop_back();
        }
        return ;
    }

public:
    vector<vector<int>> sumaDeRutas(NodoArbol* raiz, int suma) {
        if (raiz == NULL) return respuestas;
        rutaActual.push_back(raiz->valor);
        recorrer(raiz, suma - raiz->valor);
        return respuestas;
    }
};

106. Construcción de Árbol Binario a partir de Recorridos Inorden y Postorden 105. Construcción a partir de Preorden e Inorden

En esencia, los pasos son:

1. Identificar la posición de la raíz en los arrays de preorden/postorden para dividir el array inorden
2. Dividir los arrays de preorden/postorden según el tamaño de las porciones resultantes del inorden
3. Volver a identificar las raíces en los nuevos arrays

Este proceso se repite hasta que no sea posible seguir dividiendo, indicando que hemos llegado a los nodos hoja.

Las implementaciones principales difieren en cómo se procesan los arrays de preorden y postorden.

Postorden

class Solucion {
private:
    // Intervalo inorden: [inicioInorden, finInorden), intervalo postorden [inicioPostorden, finPostorden)
    NodoArbol* construirRecursivo(vector<int>& inorden, int inicioInorden, int finInorden, 
                                  vector<int>& postorden, int inicioPostorden, int finPostorden) {
        if (inicioPostorden == finPostorden) return NULL;

        int valorRaiz = postorden[finPostorden - 1];
        NodoArbol* raiz = new NodoArbol(valorRaiz);

        if (finPostorden - inicioPostorden == 1) return raiz;

        int indiceDelimitador;
        for (indiceDelimitador = inicioInorden; indiceDelimitador < finInorden; indiceDelimitador++) {
            if (inorden[indiceDelimitador] == valorRaiz) break;
        }
        // División del array inorden
        // Inorden izquierdo: [inicioInorderIzq, finInorderIzq)
        int inicioInorderIzq = inicioInorden;
        int finInorderIzq = indiceDelimitador;
        // Inorden derecho: [inicioInorderDer, finInorderDer)
        int inicioInorderDer = indiceDelimitador + 1;
        int finInorderDer = finInorden;

        // División del array postorden
        // Postorden izquierdo: [inicioPostordenIzq, finPostordenIzq)
        int inicioPostordenIzq =  inicioPostorden;
        int finPostordenIzq = inicioPostorden + indiceDelimitador - inicioInorden;
        // Postorden derecho: [inicioPostordenDer, finPostordenDer)
        int inicioPostordenDer = inicioPostorden + (indiceDelimitador - inicioInorden);
        int finPostordenDer = finPostorden - 1;

        raiz->izquierda = construirRecursivo(inorden, inicioInorderIzq, finInorderIzq, 
                                           postorden, inicioPostordenIzq, finPostordenIzq);
        raiz->derecha = construirRecursivo(inorden, inicioInorderDer, finInorderDer, 
                                          postorden, inicioPostordenDer, finPostordenDer);

        return raiz;
    }
public:
    NodoArbol* construirArbol(vector<int>& inorden, vector<int>& postorden) {
        if (inorden.size() == 0 || postorden.size() == 0) return NULL;
        // Principio de intervalos cerrados-abierto
        return construirRecursivo(inorden, 0, inorden.size(), postorden, 0, postorden.size());
    }
};

Preorden

private:
    NodoArbol* construirRecursivo(vector<int>& inorden, int inicioInorden, int finInorden, 
                                  vector<int>& preorden, int inicioPreorden, int finPreorden){
        if (inicioPreorden == finPreorden) return NULL;
        int valorRaiz = preorden[inicioPreorden];
        NodoArbol* raiz = new NodoArbol(valorRaiz);
        if (preorden.size() == 1) return raiz;
        int indiceDelimitador;
        for (indiceDelimitador = inicioInorden; indiceDelimitador < finInorden; indiceDelimitador++){
            if (inorden[indiceDelimitador] == valorRaiz) break;
        }
        // División del array inorden
        // Inorden izquierdo: [inicioInorderIzq, finInorderIzq)
        int inicioInorderIzq = inicioInorden;
        int finInorderIzq = indiceDelimitador;
        // Inorden derecho: [inicioInorderDer, finInorderDer)
        int inicioInorderDer = indiceDelimitador + 1;
        int finInorderDer = finInorden;
        
        // División del array preorden
        // Preorden izquierdo: [inicioPreordenIzq, finPreordenIzq)
        int inicioPreordenIzq =  inicioPreorden + 1;
        int finPreordenIzq = inicioPreorden + 1 + indiceDelimitador - inicioInorden;
        // Preorden derecho: [inicioPreordenDer, finPreordenDer)
        int inicioPreordenDer = inicioPreorden + 1 + (indiceDelimitador - inicioInorden);
        int finPreordenDer = finPreorden; 

        raiz->izquierda = construirRecursivo(inorden, inicioInorderIzq, finInorderIzq, 
                                           preorden, inicioPreordenIzq, finPreordenIzq);
        raiz->derecha = construirRecursivo(inorden, inicioInorderDer, finInorderDer, 
                                          preorden, inicioPreordenDer, finPreordenDer);

        return raiz;
    }
public:
    NodoArbol* construirArbol(vector<int>& preorden, vector<int>& inorden) {
        if (inorden.size() == 0 || preorden.size() == 0) return NULL;

        // Manteniendo el principio de intervalos cerrados-abierto
        return construirRecursivo(inorden, 0, inorden.size(), preorden, 0, preorden.size());
    }