给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式:
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。。
输入样例:
1 2 3
| 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7
|
输出样例:
思路
题目要求输出层序遍历,可以借助完全二叉树的思想: 某节点的左右节点索引关系分别为2 * n ,2 * n + 1。递归每次划分以左右子树,每次将当前根节点存入指定p位置,存入ans结果数组,最后直接输出即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include <iostream> #include <cstring> using namespace std; const int N = 10000; int n; int ans[N]; int post[N],mid[N]; void create(int post[],int mid[],int len,int p){ if(len < 1){ return; } int i = 0; while(post[len - 1] != mid[i]) i++; ans[p] = post[len - 1]; create(post, mid, i,2 * p); create(post + i, mid + i + 1, len - i - 1,2 * p + 1); } int main(){ scanf("%d",&n); for(int i = 0;i < n ;i++){ scanf("%d",&post[i]); } for(int i = 0;i < n; i ++){ scanf("%d",&mid[i]); } create(post, mid, n, 1); int isfir = 0; for(int i = 1;i < N ;i ++){ if(ans[i]!=0){ if(isfir) cout<<" "; isfir = 1; cout<<ans[i]; } } return 0; }
|