1102 反转二叉树

以下是来自 Max Howell @twitter 的内容：

谷歌：我们的百分之九十的工程师都使用你编写的软件，但是你连在白板上反转二叉树都做不到，还是滚吧。

现在，请你证明你会反转二叉树。

输入格式

第一行包含一个整数 N，表示树的结点数量。

所有结点编号从 0 到 N−1。

接下来 N 行，每行对应一个 0∼N−1 的结点，给出该结点的左右子结点的编号，如果该结点的某个子结点不存在，则用 − 表示。

输出格式

输出反转后二叉树的层序遍历序列和中序遍历序列，每个序列占一行。

相邻数字之间用空格隔开，末尾不得有多余空格。

数据范围

1≤N≤10

输入样例：

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

输出样例：

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

代码实现：

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N=20;
vector<int>level,middle;
int l[N],r[N],vis[N];
void dfs(int x){
    if(r[x]!=-1)dfs(r[x]);
    middle.push_back(x);
    if(l[x]!=-1)dfs(l[x]);
}
void bfs(int x){
    queue<int>q;
    q.push(x);
    while(q.size()){
        int t=q.front();
        q.pop();
        level.push_back(t);
        if(r[t]!=-1)q.push(r[t]);
        if(l[t]!=-1)q.push(l[t]);
    }
}
int main(){
    int n;
    cin>>n;
    memset(l,-1,sizeof l);
    memset(r,-1,sizeof r);
    for(int i=0;i<n;i++){
        char x,y;
        cin>>x>>y;
        if(x!='-')l[i]=(x-'0'),vis[x-'0']=1;
        if(y!='-')r[i]=(y-'0'),vis[y-'0']=1;
    }
    int root=-1;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            root=i;
            break;
        }
    }
    dfs(root);
    bfs(root);
    for(int i=0;i<level.size();i++){
        if(i==0)cout<<level[i];
        else cout<<" "<<level[i];
    }
    cout<<endl;
    for(int i=0;i<middle.size();i++){
        if(i==0)cout<<middle[i];
        else cout<<" "<<middle[i];
    }
    return 0;
}