传送
题目给定一颗二叉树，要求输出反转后二叉树的层序遍历序列和中序遍历序列
【PTA|PAT 1012Invert a Binary Tree反转二叉树（反转树，层序，中序）】关于反转操作，后序或者先序都可以
#include
#define rep(i,a,n) for(int i=a;
inode[N];
vectorans,res;
void gao(int root){
if(root==-1) return ;
gao(node[root].x);
gao(node[root].y);
swap(node[root].x,node[root].y);
}
void bfs(int root){
queueq;
q.push(root);
while(!q.empty()){
int p=q.front();
q.pop();
ans.push_back(p);
if(node[p].x!=-1) q.push(node[p].x);
if(node[p].y!=-1) q.push(node[p].y);
}
rep(i,0,ans.size())
printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
}void dfs(int root){
if(node[root].x!=-1)dfs(node[root].x);
res.push_back(root);
if(node[root].y!=-1)dfs(node[root].y);
return ;
}
int vis[N];
int main(){
cin>>n;
rep(i,0,n) {
char a,b;
cin>>a>>b;
if(a!='-') node[i].x=a-'0',vis[a-'0']=1;
else node[i].x=-1;
if(b!='-') node[i].y=b-'0',vis[b-'0']=1;
else node[i].y=-1;
}
int root=0;
while(vis[root]) root++;
gao(root);
bfs(root);
dfs(root);
rep(i,0,res.size())
printf("%d%c",res[i],i==res.size()-1?'\n':' ');
return 0;
}
推荐阅读
- PAT|PAT甲级 1102 Invert a Binary Tree 反转树再层序中序输出
- 码力提高题|UOJ#57./bzoj3051 【WC2013】(平面图转对偶图)
- #|数据结构之树的存储结构
- #|数据结构之二叉树深度计算