题目粗心：
给定一个二叉树(编号从0到N-1),和每个结点的左右孩子编号,把该二叉树进行反转,而后输入反转二叉树的层序遍历和中序遍历
算法思路：
这个题目有两种办法能够求解,一是依照题目要求间接将二叉树进行反转取得新的二叉树,而后再遍历。第二种就是不扭转二叉树,作镜像遍历,也即是之前先遍历左孩子,当初变成先遍历右孩子,毕竟只须要输入遍历的后果,就无需进行二叉树的反转,这里抉择用第二种,当然了,如果想要反转的话,间接应用后序遍历的办法,在最初拜访根节点的操作变动为替换其左右孩子节点即可($swap$函数就能够实现)。
取得根节点的办法：
这里应用了一个标记数组$isNotRoot$标记下标为i的节点是否为根节点，不是就是$true$,初始默认都是根节点，在每输出一行数据的时候，就阐明以后的输出节点为其余节点的孩子节点，肯定不是根节点，就将$isNotRoot$置为$true$，而后在输出结束后，遍历$isNotRoot$查找为$false$的下标$i$即为$root$。(实际上是双亲表示法)
提交后果：
AC代码：
#include <cstdio>#include <string>#include <iostream>#include <queue>using namespace std;struct Node{ int data,left,right;};int N;// 节点个数int root;// 根节点编号bool isNotRoot[20];// 判断节点是否为根节点，不是就是true。Node tree[20];void levelTravese(){ queue<int> q; q.push(root); int num = 0; while (!q.empty()){ int top = q.front(); q.pop(); printf("%d",top); if(num<N-1) printf(" "); ++num; if(tree[top].right!=-1){ q.push(tree[top].right); } if(tree[top].left!=-1){ q.push(tree[top].left); } }}int num = 0;void inOrder(int r){ if(r==-1) return; inOrder(tree[r].right); printf("%d",r); if(num<N-1) printf(" "); ++num; inOrder(tree[r].left);}int main(){ scanf("%d",&N); string s1,s2; for (int i = 0; i < N; ++i) { cin>>s1>>s2; int left,right; tree[i].data = i; if(s1!="-"){ // 是数字 left = stoi(s1); isNotRoot[left] = true;// 为左孩子节点，肯定不是根节点 tree[i].left = left; } else { tree[i].left = -1; } if(s2!="-"){ // 是数字 right = stoi(s2); isNotRoot[right] = true;// 为左孩子节点，肯定不是根节点 tree[i].right = right; } else { tree[i].right = -1; } } // 找到根节点 for (int j = 0; j < N; ++j) { if(!isNotRoot[j]){ root = j; break; } } levelTravese(); printf("\n"); inOrder(root); return 0;}