Tree Recovery（已知前序 中序 求后序遍历）

题目大意

给一个二叉树的前序遍历 中序遍历 求后序遍历（二叉树的value为char型）

代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r;
}tree[35];
int pre[35],in[35];
int create(int l1,int r1,int l2,int r2)//1-中 2-前
{
    if(l1>r1||l2>r2)
        return 0;
    int p=l1;
    while(in[p]!=pre[l2]) p++;
    int cnt = p-l1;
    int rt = pre[l2];
    tree[rt].l=create(l1,p-1,l2+1,l2+cnt);
    tree[rt].r=create(p+1,r1,l2+cnt+1,r2);
    return rt;
}
vector<int> ans;
void dfs(int rt)
{
    if(tree[rt].l>0) dfs(tree[rt].l);
    if(tree[rt].r>0) dfs(tree[rt].r);
    printf("%c",rt-1+‘A‘);
}
int main()
{
    char a[35], b[35];
    while(cin>>a>>b)
    {
        int n = strlen(a);
        memset(tree,0,sizeof(tree));
        for(int i =0;i<strlen(a);i++)
        {
            pre[i]=a[i]-‘A‘+1;
            in[i]=b[i]-‘A‘+ 1;
        }

        create(0,n-1,0,n-1);
        dfs(pre[0]);
        int f= 1;
        cout<<endl;
    }
}

Tree Recovery（已知前序 中序 求后序遍历）

原文：https://www.cnblogs.com/alexdzk/p/14689364.html