二叉树已知中序、后序求层次遍历

后序：8 9 4 10 5 2 6 7 3 1
中序：8 4 9 2 10 5 1 6 3 7

思路

1、i节点的左孩子可以表示为：2i+1，右孩子可以表示为：2i；
2、后序的最后一个节点为根节点，在中序中找到根节点所在的位置index，这样index左面全部为左子树，右面全部为右子树，再用同样的方法递归，
3、第一次递归的结果为所有的左孩子节点的值放入map中，第二次遍历为所有的右孩子，放入map。

#include <cstdio>
#include <vector>
#include <map>
using namespace std;
vector<int> post, in;
map<int, int> level;

void pre(int root, int start, int end, int index) {
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;    //找到根节点在中序中的位置
    level[index] = post[root];
    pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
    pre(root - 1, i + 1, end, 2 * index + 2);
}

int main() {
    int n;
    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]);
    pre(n-1, 0, n-1, 0);
    auto it = level.begin();
    printf("%d", it->second);
    while(++it != level.end()) printf(" %d", it->second);
    return 0;
}