題目描述

小明在做數據結構的作業，其中一題是給你一棵二叉樹的前序遍歷和中序遍歷結果，要求你寫出這棵二叉樹的后序遍歷結果。

輸入

輸入包含多組測試數據。每組輸入包含兩個字符串，分別表示二叉樹的前序遍歷和中序遍歷結果。每個字符串由不重復的大寫字母組成。

輸出

對于每組輸入，輸出對應的二叉樹的后續遍歷結果。

樣例輸入

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 testfreopen("in.txt","r",stdin);
//    freopen("in.txt","w",stdout);clock_t start=clock();#endif //testwhile(~scanf("%s%s",preorder,midorder)){getlastorder(preorder,midorder,strlen(preorder));printf("\n");}#ifdef testclockid_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 //testreturn 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 testfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);clock_t start=clock();#endif //testchar 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 testclockid_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 //testreturn 0;
}