根据前序中序求后序(树）

题目描述

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历。

输入

读入2个两个字符串，每个一行，长度均小于等于26。 

第一行为前序遍历，第二行为中序遍历。 

二叉树中的结点名称以大写字母表示：A，B，C....。

输出

输出一行，为后序遍历的字符串。

样例输入 

ABC
CBA

样例输出   

CBA

思路 

遍历前序字符串，前序遍历的每一个字符都是某个子树的根，再在中序遍历中找到根，将其分为左子树，根，右子树，依次递归，以此建树，在后序遍历一下即可（我语文不好，详见代码）

代码

#include <bits/stdc++.h>
using namespace std;
int root,key;
string q,z;
struct the_tree
{
    int l,r;
    char data;
}tree[50];
int build(int l,int r)
{
    if(l>r||l<0||r>q.size()-1||r<0||l>q.size()-1||key>q.size()-1)
    {
        return -1;
    }
    else
    {
        char c=q[key];
        for(int i=l;i<=r;i++)
        {
            if(z[i]==c)
            {
                root=i;
                break;
            }
        }
        int ls=l;
        int le=root-1;
        int rs=root+1;
        int re=r;
        int x=++key;
        tree[x].data=c;
        tree[x].l=build(ls,le);
        tree[x].r=build(rs,re);
        return x;
    }
}
void hx(int step)
{
    if(step!=-1)
    {
        hx(tree[step].l);
        hx(tree[step].r);
        cout<<tree[step].data;
    }
}
int main()
{
    cin>>q>>z;
    build(0,q.size()-1);
    hx(1);
    return 0;
}