PAT 乙级的一道题目，题目描述：

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例： 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例： 4 1 6 3 5 7 2

原文链接：https://www.patest.cn/contests/gplt/L2-006

一道二叉树的重建类型问题，根据后序遍历的顺序我们可以知道，输出的最后一个节点的值就是整个二叉树的根节点。我们在中序遍历中找到它的位置，那么左右两边的节点就是该节点的左右子树，之后找到后续遍历的倒数第二个节点，这个就是根节点的右子节点，然后再对这个节点进行讨论。。。

如果小伙伴还是不太懂的话，可以参考一下这篇文章，思路原理都是相同的：http://blog.csdn.net/hacker_zhidian/article/details/60770262

Ok，下面给出AC代码：

#include <iostream>
#include <algorithm>
#include <queue> 
using namespace std;
const int INF = -99999999; // 节点不存在的时候赋值给节点 
const int N = 10010;

int in[N];
int post[N];
int pos;

struct Node { // 储存节点信息的结构体 
    int w; // 值 
    int l; // 左子节点的下标 
    int r; // 右子节点的下标 
};
Node node[N];


void input(int a[], int n) {
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

}

// 重建以第 n 个节点为根节点的二叉树 
void rec(int l, int r, int n) {
    if(l >= r) {
        node[n].w = INF; // 如果节点不存在，赋值为 INF 
        return ;
    }
    int root = post[pos--]; // 获取后续遍历中节点的数值 
    node[n].w = root;
    node[n].l = 2*n; // 左子树所在数组下标 
    node[n].r = 2*n+1; // 右子树所在数组下标 
    int m = find(in, in+r, root) - in;

    rec(m+1, r, 2*n+1); // 因为是后序遍历，所以先重建右子树 
    rec(l, m, 2*n); // 在重建左子树 
}

// 使用 C++ STL 模板提供的队列数据结构 
void print() {
    queue<int> que;
    que.push(1); // 将 1 号节点入队
    int index;
    while(!que.empty()) {
        index = que.front(); // 取出队头元素 
        que.pop(); // 对头元素出队 
        if(node[index].w != INF) {
            if(index != 1) {
                cout << " ";
            }
            cout << node[index].w;
            que.push(node[index].l);
            que.push(node[index].r);
        }
    }
}

int main() {
    int n;
    cin >> n;
    pos = n - 1;
    input(post, n);
    input(in, n);

    rec(0, n, 1);

    print();

    return 0;
}

如果博客中有什么不正确的地方，还请多多指点。如果觉得我写的不错，请点个赞表示对我的支持吧。

谢谢观看。。。