题目描述

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

输入格式

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

思路：

核心思想是给定一个二叉树后序序列和中序序列，要求还原这棵二叉树。
需要把中序序列的值和其对应的下标存入哈希表中，方便利用后序序列进行还原。
最后采用bfs来输出结果。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node *left;
    Node *right;
    Node(int x) : val(x), left(NULL),right(NULL) {}
};

int n,idx;
unordered_map<int,int> mp;
vector<int> post,in,ans;
Node *build(vector<int> &post,int l,int r);
Node *T;

//利用bfs进行层序遍历，并输出每一个结果
void bfs()
{
    queue<Node*> q;
    q.push(T);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        ans.push_back(t->val);
        if(t->left) q.push(t->left);
        if(t->right) q.push(t->right);  
    }

    for(int i=0;i<ans.size();i++)
    {
        if(i==0) cout<<ans[i];
        else cout<<" "<<ans[i]; 
    }   
}

int main()
{
    cin>>n;
    int x;
    for(int i=0;i<n;i++) cin>>x,post.push_back(x);
    for(int i=0;i<n;i++) cin>>x,in.push_back(x);

    for(int i=0;i<n;i++) mp[in[i]]=i; //将中序序列的值与下标用哈希表对应起来
    idx=n-1;    //二叉树根节点在后序序列中的下标idx
    T = build(post,0,n-1);
    bfs();
    return 0;
}

//构建二叉树
Node *build(vector<int> &post,int l,int r)
{
    if(l>r) return NULL;

    int pos=mp[post[idx]];
    Node *root=new Node(post[idx--]);

    //递归构造二叉树
    root->right=build(post,pos+1,r);
    root->left=build(post,l,pos-1); 
    return root;
}