//1102 Invert a Binary Tree法二 算法下P292 法一 【二叉树】
#include <iostream>
#include <queue>
#define maxSize 20
using namespace std;
struct BTNode{
int data;
int lChild,rChild;
};
BTNode nodes[maxSize];
void levelOrder(int root){
queue<int> q;
if(root != -1) q.push(root);
int flag = 0;
while(!q.empty()){
int k = q.front();
if(!flag){
cout<< nodes[k].data;
flag = 1;
}else cout<<" "<<nodes[k].data;
q.pop();
if(nodes[k].rChild != -1) q.push(nodes[k].rChild);
if(nodes[k].lChild != -1) q.push(nodes[k].lChild);
}
}
//逆向中序遍历
int flag = 0;
void inOrder(int root){
if(root == -1) return;
inOrder(nodes[root].rChild);
if(!flag){
cout << nodes[root].data;
flag = 1;
}else cout<<" "<<nodes[root].data;
inOrder(nodes[root].lChild);
}
int main(){
int N;
char lChar,rChar;
int hash[maxSize] = {0};
for(int i=0;i<maxSize;++i){
nodes[i].data = -1; //自己：这个data没啥用
nodes[i].lChild = -1;
nodes[i].rChild = -1;
}
cin>>N;
for(int i=0;i<N;++i){
cin >> lChar >> rChar;
if(lChar != '-'){
nodes[i].lChild = lChar - '0';
hash[lChar - '0'] = 1;
}
if(rChar != '-'){
nodes[i].rChild = rChar - '0';
hash[rChar - '0'] = 1;
}
nodes[i].data = i;
}
int root;
for(int i=0;i<N;i++){
if(!hash[i]){
root = i;
break;
}
}
levelOrder(root);
cout<<endl;
inOrder(root);
return 0;
}
