给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
1 #include<iostream> 2 #include<queue> 3 using namespace std; 4 //结点权值作为结点编号 5 int postOrder[31]; //后序遍历结点 6 int inOrder[31]; //中序遍历结点 7 int leftNodes[31]; //保存某结点的左子树编号 8 int rightNodes[31]; //保存某结点的右子树编号 9 10 //根据inOrder[L1]到inOrder[R1] 和postOrder[L1]到postOrder[R1]的结点编号 来构建树 11 //返回根节点 12 int buildTree(int L1, int R1, int L2, int R2){ 13 if (R1 < L1) //空树 14 return -1; 15 int root = postOrder[R2]; //后序遍历序列最后一个结点一定是根结点 16 int p =0; 17 while (inOrder[p] != root) //找到中序遍历序列中对应哪个根结点的结点 18 p++; 19 int count = p - L1; //左子树结点总数 20 21 //p是中序序列的根，从L1到p-1为左子树，对应的后续序列的从L2到L2+count-1 22 leftNodes[root] = buildTree(L1, p- 1, L2, L2 + count - 1); 23 //中序序列从p+1到R1为右子树，对应的后续序列从L2+count到R2 - 1 ！！因为根节点已经去掉了！！ 24 rightNodes[root] = buildTree(p + 1, R1, L2+count, R2-1); 25 return root; 26 } 27 28 //层序遍历 29 //传了个N进去是因为输出格式控制 = = 30 void printVex(int root,int N){ 31 queue<int> q; 32 q.push(root); 33 while (q.size()){ 34 int vex = q.front(); 35 if (N==1) 36 cout << vex; 37 else 38 cout << vex<<" "; 39 q.pop(); 40 if (leftNodes[vex] != -1) 41 q.push(leftNodes[vex]); 42 if (rightNodes[vex] != -1) 43 q.push(rightNodes[vex]); 44 N--; 45 } 46 } 47 int main(){ 48 int N; 49 cin >> N; 50 int index = 0; 51 for (int i = 1; i <= N; i++){ 52 int vex; 53 cin >> vex; 54 postOrder[index++] = vex; 55 } 56 index = 0; 57 for (int j = 1; j <= N; j++){ 58 int vex; 59 cin >> vex; 60 inOrder[index++] = vex; 61 } 62 int root = buildTree(0, N - 1, 0, N - 1); 63 printVex(root,N); 64 return 0; 65 }