思路：题目要求由先序序列和中序序列得出后序序列，由先序序列和中序序列的定义（根左右，左根右）可以知道先序序列的第一个节点一定是一个二叉树的顶点，我们可以在中序序列中找到这个顶点的位置，即可判断这个二叉树的左右子树的节点，重复此过程，我们就完成了建树。
每次建树先找到子树的父节点，再在先序序列和中序序列中截取相同且对应的节点元素，来完成对子树的创建。

题目描述

先序序列+中序序列建立二叉树

输入样例

第一行输入序列长度n，第二行输入n个字符表示二叉树先序遍历的序列，第三行输入n个字符表示二叉树中序遍历的序列

9
ABDGHCEFI
GDHBAECIF

输出样例

输出二叉树后序遍历的序列。

GHDBEIFCA

方法1

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;
struct Node{
    char data;
    Node* l;
    Node* r;
};//存储每个节点的基本信息

string pre,in;//存储先序序列和中序序列

//pl,pr分别是每次建树需要的先序序列的开始和结束位置，il和ir分别是每次建树需要的中序序列开始和结束位置。root则是每次建树的父节点。
void build(Node *&root, int pl, int pr, int il, int ir)
{
    if(pl <= pr && il <= ir)
    {
        root = new Node;
        root->data = pre[pl];
        root->l = root->r = NULL;

        int index;
        for(index = il; index <= ir; index++)
        {
            if(in[index] == pre[pl])//在中序序列中找到顶点位置
                break;
        }
        int numLeft = index - il;//左子树的长度

        build(root->l, pl+1, pl+numLeft, il, index-1);//建立左子树，上一二叉树的父节点为先序序列的开始位置，则建立下一左子树时，它的父节点就在先序序列的开始位置加一了，同时在中序序列中，index此时为上一二叉树的父节点，il到index-1也就为左子树所有节点元素在中序序列中的位置）
        build(root->r, pl+numLeft+1, pr, index+1, ir);//建立右子树，同理。
    }
}

void post(Node* root)//按左右根的次序输出，即为后序序列
{
    if(root != NULL)
    {
        post(root->l);
        post(root->r);
        cout << root->data;
    }
}

int main()
{
    int n;
    cin >> n >> pre >> in;

    Node* root;//建立一个根节点，用来建树。
    build(root,0,n-1,0,n-1);
    post(root);//在调用节点进行操作时一定使用->

    return 0;
}

方法2

参考某位不知情人士的高级代码🤫🤫

省略了建造结构体的过程，且在搜索时间上进行了优化

C++ 代码

//先序序列+中序序列建立二叉树（边建树边输出） 
#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;
string pre,in;//存先序序列和中序序列

unordered_map<char,int> mp;//用unordered_map来对中序序列的每一个元素位置进行存储，使得找父节点的复杂度降低

void build(int pl, int pr, int il, int ir)
{
    char root = pre[pl];//找到先序序列中的父节点
    int k = mp[root];//直接得出父节点在中序序列的位置

    if(k > il)//保证左子树长度大于0 
        build(pl+1,pl+k-il,il,k-1);//k-il为左子树的长度
    if(k < ir)//保证右子树长度大于0 
        build(pl+1+k-il,pr,k+1,ir);
    cout << root;//根据左右根顺序对其进行后序序列输出
}

int main()
{
    int n;
    cin >> n >> pre >> in;
    for(int i = 0; i < n; i++)
    {
        mp[in[i]] = i;
    }
    build(0,n-1,0,n-1);
    return 0;
}