[声明]本解法直接采用rch[]和lch[]两个数组来存储二叉树的信息，从程序的写法来看比《算法笔记》上的解法会更简单些； 1. 题目链接：https://www.patest.cn/contests/pat-a-practise/1102 2. 解题思路：直接存储翻转后的二叉树信息；然后层次和中序遍历输出即可； 3. AC代码：
#include<cstdio> #include<queue> #include<cstring> using namespace std; int n,lch[20],rch[20]; //层次遍历 int num=0;//用于判断是否要输出空格 void bfs(int root){ queue<int> q; q.push(root); while(!q.empty()){ int p=q.front();q.pop(); num++; printf("%d",p); if(num<n) printf(" "); if(lch[p]!=-1) q.push(lch[p]); if(rch[p]!=-1) q.push(rch[p]); } printf("\n"); return; } //中序遍历 void dfs(int root){ if(root==-1) return; dfs(lch[root]); printf("%d",root);num++;if(num<n) printf(" "); dfs(rch[root]); } int main(){ scanf("%d",&n);getchar();char str[4]; int hash[20];//都有可能是根节点 memset(hash,1,sizeof(hash)); for(int i=0;i<n;i++){ gets(str); if(str[0]=='-') rch[i]=-1;else {rch[i]=str[0]-'0';hash[str[0]-'0']=0;} if(str[2]=='-') lch[i]=-1;else {lch[i]=str[2]-'0';hash[str[2]-'0']=0;} }//完成翻转和建树 int root; for(int i=0;i<n;i++) if(hash[i]) root=i;//找到根节点 bfs(root);//层次遍历 num=0; dfs(root);//中序遍历 return 0; }