《算法笔记》9.2小节——数据结构专题(2)-＞二叉树的遍历 问题 A: 复原二叉树（同问题 C: 二叉树遍历）

题目描述

小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。

输入

输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。

输出

对于每组输入，输出对应的二叉树的后续遍历结果。

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB

分析：不建树直接找的方法。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define ll long long
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,a) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<endl
using namespace std;
 
char preorder[1100],midorder[1100],lastorder[1100];
 
void getlastorder(char pre[],char mid[],int n)
{
    int t;
    if(n<=0)return;
    for(t=0;t<n;++t)
        if(mid[t]==pre[0])break;
    getlastorder(pre+1,mid,t);
    getlastorder(pre+t+1,mid+t+1,n-t-1);
    printf("%c",pre[0]);
}
 
int main(void)
{
    #ifdef test
    freopen("in.txt","r",stdin);
//    freopen("in.txt","w",stdout);
    clock_t start=clock();
    #endif //test
 
    while(~scanf("%s%s",preorder,midorder))
    {
        getlastorder(preorder,midorder,strlen(preorder));
        printf("\n");
    }
 
    #ifdef test
    clockid_t end=clock();
    double endtime=(double)(end-start)/CLOCKS_PER_SEC;
    printf("\n\n\n\n\n");
    cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位
    cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位
    #endif //test
    return 0;
}

建树再后序遍历的方法：由于前序遍历是先遍历根节点，因此前序遍历的第一个点一定是根节点。再到中序遍历中找到根节点的位置，这之前都是左子树，这之后都是右子树。知道左右子树长度之后，就可以在前序遍历中找到左右子树。这样递归地建立二叉树，最后输出后序遍历结果。

#include    <algorithm>
#include     <iostream>
#include      <cstdlib>
#include      <cstring>
#include       <string>
#include       <vector>
#include       <cstdio>
#include        <queue>
#include        <stack>
#include        <ctime>
#include        <cmath>
#include          <map>
#include          <set>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,a) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<endl
#define db5(x,y,z,a,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<", "<<#r<<"="<<(r)<<endl
using namespace std;

typedef struct node
{
    char val;
    struct node *left,*right;
}node;

void Free(node *root)
{
    if(root->left!=NULL)Free(root->left);
    if(root->right!=NULL)Free(root->right);
    free(root);
    return;
}

node *get_tree(char *pre,int pre_l,int pre_r,char *mid,int mid_l,int mid_r)
{
    if(pre_l>=pre_r)return NULL;

    node *p=(node *)malloc(sizeof(node));
    p->val=pre[pre_l];

    int index=0;
    for(index=mid_l;index<mid_r;++index)
        if(mid[index]==pre[pre_l])
            break;

    p->left=get_tree(pre,pre_l+1,pre_l+1+index-mid_l,mid,mid_l,index);
    p->right=get_tree(pre,pre_l+1+index-mid_l,pre_r,mid,index+1,mid_r);

    return p;
}

void last_order(node *root)
{
    if(root==NULL)return;
    last_order(root->left);
    last_order(root->right);
    printf("%c",root->val);
    return;
}

int main(void)
{
    #ifdef test
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    clock_t start=clock();
    #endif //test

    char pre[100000],mid[100000];
    while(~scanf("%s%s",pre,mid))
    {
        int len=strlen(pre);
        node *root=get_tree(pre,0,len,mid,0,len);
        last_order(root);
        printf("\n");
        Free(root);
    }

    #ifdef test
    clockid_t end=clock();
    double endtime=(double)(end-start)/CLOCKS_PER_SEC;
    printf("\n\n\n\n\n");
    cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位
    cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位
    #endif //test
    return 0;
}