【PAT甲级】1102 Invert a Binary Tree (25 分)(层次遍历和中序遍历)

时间:2021-05-23 20:19:34

题意:

输入一个正整数N(<=10),接着输入0~N-1每个结点的左右儿子结点,输出这颗二叉树的反转的层次遍历和中序遍历。

AAAAAccepted code:

 #define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[][];
bool vis[];
void bfs(int r){
queue<int>q;
q.push(r);
cout<<r;
while(!q.empty()){
int now=q.front();
q.pop();
if(a[now][]!=-){
cout<<" ";
cout<<a[now][];
q.push(a[now][]);
}
if(a[now][]!=-){
cout<<" ";
cout<<a[now][];
q.push(a[now][]);
}
}
}
int flag=;
void dfs(int r){
if(a[r][]!=-)
dfs(a[r][]);
if(flag)
cout<<" ";
cout<<r;
flag=;
if(a[r][]!=-)
dfs(a[r][]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for(int i=;i<;++i)
a[i][]=a[i][]=-;
int n;
cin>>n;
for(int i=;i<n;++i){
char x;
cin.ignore();
cin>>x;
cin.ignore();
if(x!='-')
a[i][]=x-'',vis[x-'']=;
char y;
cin>>y;
if(y!='-')
a[i][]=y-'',vis[y-'']=;
}
int root=;
for(int i=;i<n;++i)
if(!vis[i])
root=i;
bfs(root);
cout<<"\n";
dfs(root);
return ;
}