En una publicación de Twitter, Max Howell mencionó: "Google: el 90% de nuestros ingenieros usan el software que desarrollaste (Homebrew), pero no puedes invertir un árbol binario en una pizarra, así que no eres apto." Ahora es tu oportunidad de demostrar que sí puedes lograrlo.

Especificación de Entrada:

Cada archivo de entrada contiene un caso de prueba. Para cada caso, la primera línea proporciona un entero positivo N (≤10) que indica el número total de nodos en el árbol, numerados del 0 al N-1. Luego siguen N líneas, cada una correspondiente a un nodo del 0 al N-1, que especifica los índices de los hijos izquierdo y derecho del nodo. Si un hijo no existe, se coloca un guion (-) en esa posición. Los índices de los hijos están separados por un espacio.

Especificación de Salida:

Para cada caso de prueba, imprime en la primera línea el recorrido por niveles, y en la segunda línea el recorrido en orden del árbol invertido. Debe haber exactamente un espacio entre números adyacentes, sin espacios adicionales al final de la línea.

Ejemplo de Entrada:

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Ejemplo de Salida:

3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1

A continuación, se presenta una implementación en C++ que resuelve el problema. El código construye el árbol a partir de la entrada, lo invierte intercambiando los hijos izquierdo y derecho de cada nodo, y luego genera los recorridos requeridos. Se han modificado los nombres de las variables y la estructura para reducir la similitud con el origianl.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct NodoArbol {
    int izquierdo = -1;
    int derecho = -1;
};

vector<int> recorridoEnOrden;
vector<int> recorridoPorNivel;

void construirEnOrden(int raiz, const vector<NodoArbol>& arbol) {
    if (raiz == -1) return;
    construirEnOrden(arbol[raiz].izquierdo, arbol);
    recorridoEnOrden.push_back(raiz);
    construirEnOrden(arbol[raiz].derecho, arbol);
}

void construirPorNivel(int raiz, const vector<NodoArbol>& arbol) {
    queue<int> cola;
    cola.push(raiz);
    while (!cola.empty()) {
        int nodoActual = cola.front();
        cola.pop();
        recorridoPorNivel.push_back(nodoActual);
        if (arbol[nodoActual].izquierdo != -1) cola.push(arbol[nodoActual].izquierdo);
        if (arbol[nodoActual].derecho != -1) cola.push(arbol[nodoActual].derecho);
    }
}

void invertirArbol(int raiz, vector<NodoArbol>& arbol) {
    if (raiz == -1) return;
    swap(arbol[raiz].izquierdo, arbol[raiz].derecho);
    invertirArbol(arbol[raiz].izquierdo, arbol);
    invertirArbol(arbol[raiz].derecho, arbol);
}

int main() {
    int cantidadNodos;
    cin >> cantidadNodos;

    vector<NodoArbol> arbol(cantidadNodos);

    for (int i = 0; i < cantidadNodos; ++i) {
        char hijoIzq, hijoDer;
        cin >> hijoIzq >> hijoDer;
        if (hijoIzq != '-') arbol[i].izquierdo = hijoIzq - '0';
        if (hijoDer != '-') arbol[i].derecho = hijoDer - '0';
    }

    // Encontrar la raíz (nodo sin padre)
    vector<bool> tienePadre(cantidadNodos, false);
    for (int i = 0; i < cantidadNodos; ++i) {
        if (arbol[i].izquierdo != -1) tienePadre[arbol[i].izquierdo] = true;
        if (arbol[i].derecho != -1) tienePadre[arbol[i].derecho] = true;
    }
    int raiz = -1;
    for (int i = 0; i < cantidadNodos; ++i) {
        if (!tienePadre[i]) {
            raiz = i;
            break;
        }
    }

    // Invertir el árbol
    invertirArbol(raiz, arbol);

    // Realizar recorridos
    recorridoEnOrden.clear();
    recorridoPorNivel.clear();
    construirEnOrden(raiz, arbol);
    construirPorNivel(raiz, arbol);

    // Imprimir recorrido por niveles
    for (size_t i = 0; i < recorridoPorNivel.size(); ++i) {
        if (i > 0) cout << " ";
        cout << recorridoPorNivel[i];
    }
    cout << endl;

    // Imprimir recorrido en orden
    for (size_t i = 0; i < recorridoEnOrden.size(); ++i) {
        if (i > 0) cout << " ";
        cout << recorridoEnOrden[i];
    }
    cout << endl;

    return 0;
}