给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
72 3 1 5 7 6 41 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
#include#include #include #include #include #include using namespace std;const int N = 50 + 5;struct node{ int key, lchild, rchild; node(){ lchild = rchild = 0; }}Node[N];vector post, in;int n, key, st;void DFS(int &root, int ls, int lt, int is, int it){ if(root == 0) root = ++st; int p = post[lt]; Node[root].key = p; int pos = is; while(in[pos] != p) pos++; if(pos != is){ DFS(Node[root].lchild, ls, ls + pos - is - 1, is, pos - 1); } if(pos != it){ DFS(Node[root].rchild, ls + pos - is, lt - 1, pos + 1, it); }}void BFS(int root){ int cnt = 0; queue Q; Q.push(root); while(!Q.empty()){ int tmp = Q.front(); Q.pop(); printf("%d%c", Node[tmp].key, ++cnt == n?'\n':' '); if(Node[tmp].lchild){ Q.push(Node[tmp].lchild); } if(Node[tmp].rchild){ Q.push(Node[tmp].rchild); } }}int main(){ scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%d", &key); post.push_back(key); } for(int i = 0; i < n; i++){ scanf("%d", &key); in.push_back(key); } int root = 0; st = 0; DFS(root, 0, n-1, 0, n-1); BFS(root);}