共计 1283 个字符，预计需要花费 4 分钟才能阅读完成。
并查集用多了。。。第一时间想到的是并查集却没有想到静态数组，这是一个比较大的失误；这道题的关键在于如下几个点：1. 如何保存输入的树；2. 如何寻找根节点；3. 如何完成树的反转；1，2 两点都很容易解决，可能比较难一点的是第三点；其实第三点也不难，我们观察一下就可以知道，树的反转本身就是在后序遍历的过程中对左右子树进行对换，就可以很轻松的得到反转后的树；总体代码如下所示：
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=110;
struct node{
int lchild;
int rchild;
}Node[maxn];
bool noRoot[maxn]={false};
int n,num=0;
void print(int id){
printf(“%d”,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 postOrder(int root){
if(root==-1)
return;
postOrder(Node[root].lchild);
postOrder(Node[root].rchild);
swap(Node[root].lchild,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);
}
}
int strTonum(char c){
if(c==’-‘)
return -1;
else{
noRoot[c-‘0’]=true;
return c-‘0’;
}
}
int findRoot(){
for(int i=0;i<n;i++){
if(noRoot[i]==false){
return i;
}
}
}
int main(){
char lchild,rchild;
scanf(“%d”,&n);
for(int i=0;i<n;i++){
scanf(“%*c%c %c”,&lchild,&rchild);
Node[i].lchild=strTonum(lchild);
Node[i].rchild=strTonum(rchild);
}
int root=findRoot();
postOrder(root);
BFS(root);
num=0;
inOrder(root);
system(“pause”);
return 0;
}
