给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数N(≤),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式:
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
输入样例:
72 3 1 5 7 6 41 2 3 4 5 6 7
输出样例:
4 1 6 3 5 7 2
代码:
#includeusing namespace std;const int maxn = 1e5 + 10;int N;vector post, in;vector level(maxn, -1);void levelorder(int inl, int inr, int root, int index) { if(inl > inr) return ; int i = inl; while(i < inr && in[i] != post[root]) i ++; level[index] = post[root]; levelorder(inl, i - 1, root - inr + i - 1, index * 2 + 1); levelorder(i + 1, inr, root - 1,index * 2 + 2);}int main() { scanf("%d", &N); post.resize(N), in.resize(N); for(int i = 0; i < N; i ++) scanf("%d", &post[i]); for(int i = 0; i < N; i ++) scanf("%d", &in[i]); levelorder(0, N - 1, N - 1, 0); int cnt = 0; for(int i = 0; i < maxn; i ++) { if(level[i] != -1 && cnt != N - 1) { printf("%d ", level[i]); cnt ++; } else if(level[i] != -1 && cnt == N - 1) { printf("%d", level[i]); break; } } return 0;}
植树节快落
FH