PAT 甲级 1020 Tree Traversals

https://pintia.cn/problem-sets/994805342720868352/problems/994805485033603072

?

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences,you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case,the first line gives a positive integer?N?(≤),the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case,print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space,and there must be no extra space at the end of the line.

Sample Input:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

代码：

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> in,post,level(100000,-1);

void rec(int root,int st,int en,int index) {
    if(st > en) return;
    int i = st;
    while(i < en && in[i] != post[root]) i ++;
    level[index] = post[root];
    rec(root - 1 - en + i,st,i - 1,2 * index + 1);
    rec(root - 1,i + 1,en,2 * index + 2);
}

int main() {
    scanf("%d",&N);
    in.resize(N),post.resize(N);
    for(int i = 0; i < N; i ++)
        scanf("%d",&post[i]);
    for(int i = 0; i < N; i ++)
        scanf("%d",&in[i]);

    rec(N - 1,N - 1,0);
    int cnt = 0;
    for(int i = 0; i < level.size(); i ++) {
        if(level[i] != -1) {
            if(cnt) printf(" ");
            printf("%d",level[i]);
            cnt ++;
        }
        if(cnt == N) break;
    }
    return 0;
}

　　已知后序中序求层序遍历的结果?

　　vector<int> level(100000,-1); 这句话很有必要