/*
题意：
1、给出一棵树
2、然后要求给出层次，以及交换左右子树的中序

解题：
1、结构体
2、打印函数
3、中序遍历
4、层次遍历
5、后序遍历反转二叉树
6、将输入的字符转为编号，同时置为true，表示节点
7、寻找根节点
8、读入数，并且找根节点，根节点反转，然后调用层序，中序遍历

learn && wrong:
1、不会建树，读取两个字符，并将它们转为数字，用for逐个修改左右节点就是数了！（当然前提要创建个数组）
2、如何交换左右子树，后序遍历可以交换左右子树
3、先序其实也可以，不过好像挺麻烦的

*/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int maxn = 110;
struct node {
    
    int lchild; //指向左子树的指针域
    int rchild; //指向右子树的指针域
}Node[maxn];

bool notRoot[maxn] = { false }; //记录是否不是 根节点，初始均是根节点
int n, num = 0;                 //n为节点个数，num为当前已经输出的节点个数

//print函数输出节点id的编号

void print(int id) {
    printf("%d", id);   //输出id
    num++;
    if (num < n) printf(" ");   //最后一个节点不加空格
    else printf("\n");
}

//中序遍历
void inorder(int root) {
    if (root == -1) {
        return;
    }
    inorder(Node[root].lchild);
    print(root);
    inorder(Node[root].rchild);
}

void BFS(int root) {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        print(now);
        if (Node[now].lchild != -1) {
            q.push(Node[now].lchild);
        }
        if(Node[now].rchild != -1){
            q.push(Node[now].rchild);
        }
    }
}
//后序遍历，反转二叉树
void postorder(int root) {
    if (root == -1) {
        return;
    }
    postorder(Node[root].lchild);
    postorder(Node[root].rchild);
    swap(Node[root].lchild, Node[root].rchild); //交换左右孩子节点
}

//将输入的字符转为为-1或者节点编号
int strtonum(char c) {
    if (c == '-') { //’-’表示没有孩子节点，记为-1
        return -1;
    }
    else {
        notRoot[c - '0'] = true; //标记C不是节点
        return c - '0';             //返回节点
    }
}

int findroot() {
    for (int i = 0;i < n;i++) {
        if (notRoot[i] == false) {
            return i;       //是根节点，返回i
        }
    }
}

int main()
{
    char lchild, rchild;
    scanf_s("%d", &n);    //节点个数
    getchar();
    for (int i = 0;i < n;i++) {
        scanf("%c %c", &lchild, &rchild);
        getchar();
        Node[i].lchild = strtonum(lchild);
        Node[i].rchild = strtonum(rchild);
    }

    int root = findroot();
    postorder(root);    //后序遍历，反转二叉树
    BFS(root);  //输出层序遍历序列

    num = 0;    //已经输出的节点个数清0
    inorder(root);  //输出中序遍历序列
    return 0;
}