二叉树遍历

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

输入格式：

输入第一行给出一个正整数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

分析

对于后序遍历序列 ： 最后一个值是根，前面一部分是左儿子 ， 中间一部分是右儿子。
比如样例 ： 4 是根 ， 231 是左儿子 ， 576 是右儿子。

如何找到哪一段是左儿子，哪一段是右儿子 ？

看中序遍历序列 ： 在中序遍历序列中找到根 4 。 它左边有3个数，全是它的左儿子。右边同理。
这样就找到左儿子是有三个数 ， 右儿子是有 3 个数的，这样看回后序遍历序列。就知道前三个数是左儿子，紧接着的3个数是右儿子。

就这样慢慢还原一棵树。然后bfs层序输出。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#define CLR(x) memset(x,0,sizeof(x))
#define LL long long
using namespace std;
int mid[50],hou[50];

struct node{
    int l , r;
}a[50];

int build(int la,int ra,int lb,int rb){
    if(la > ra) return 0;
    int rt = hou[rb];
    int p1 = la , p2 ;
    while(mid[p1] != rt) p1++;
    p2 = p1 - la;
    a[rt].l = build(la,p1-1,lb,lb+p2-1);
    a[rt].r = build(p1+1,ra,lb+p2,rb-1);
    return rt;
}

void bfs(int x)
{
    queue<int> q;
    vector<int> g;
    q.push(x);
    while(!q.empty()){
        int w = q.front();
        q.pop();
        if(w == 0) break;
        g.push_back(w);
        if(a[w].l != 0){
            q.push(a[w].l);
        }
        if(a[w].r != 0){
            q.push(a[w].r);
        }
    }
    for(int i = 0 ; i < g.size() ; i++){
        printf("%d%c",g[i],i==g.size()-1 ? '\n' : ' ');
    }
    return;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++) cin >> hou[i];
    for(int i = 0 ; i < n ; i++) cin >> mid[i];
    build(0,n-1,0,n-1);
    int root = hou[n-1];
    bfs(root);
}