【CCCC】L2-006 树的遍历 (25分)，根据后序与中序遍历建立二叉树

problem

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

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

problem

• 题意：给出二叉树中序和后序遍历，求层次遍历
• 建树：根据后序已知根，然后去中序里面找，找到后划分左右子树递归。
• BFS遍历：按照Tree(l,r)层次遍历，vector累加答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 55;

int n, post[maxn], mid[maxn];
struct node{int l, r;}tree[maxn];
int build(int l1, int r1, int l2, int r2){//分别对应中序和后序的左右边界
    if(l1 > r1)return 0;
    int rt = post[r2], prt = l1;//1.后序确定根
    while(mid[prt]!=rt)prt++;//2.中序找根的位置
    int cnt = prt-l1;//3.中序确定左子树节点树
    tree[rt].l = build(l1,prt-1,l2,l2+cnt-1);//4.递归左子树
    tree[rt].r = build(prt+1,r1,l2+cnt,r2-1);//5.递归右子树
    return rt;
}

vector<int>ans;
void bfs(int rt){
    queue<int>q; q.push(rt);
    ans.push_back(rt);
    while(q.size()){
        int u = q.front();  q.pop();
        if(tree[u].l != 0){
            q.push(tree[u].l);
            ans.push_back(tree[u].l);
        }
        if(tree[u].r != 0){
            q.push(tree[u].r);
            ans.push_back(tree[u].r);
        }
    }
    for(int i = 0; i < ans.size()-1; i++)
        cout<<ans[i]<<" ";
    cout<<ans[ans.size()-1];
}


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