原题：
给出一棵二叉树的中序与后序排列。求出它的先序排列。
性质：
1.三序遍历的序列中，同一子树的所有节点不留空隙地组成一个区间，即对于任意子树，存在一个区间使得区间内每个点都恰好是子树中的一个节点
2.中序遍历序列中，在一个子树的区间中，子树根节点左边的区间是左子树区间，右边的区间是右子树区间
3.后序遍历序列中，一个子树区间内，子树根节点左边是右子树区间，再左边是左子树区间
4.由上可以推出在某个字数区间中，后序遍历标号最大的节点是根节点
那么可以递归，参数为中序遍历序列中子树的区间端点，每次在子树区间中找到后序遍历标号最大的点，即子树根节点，然后递归处理左右子树区间
代码：（题目中不同节点用不同大写字母表示）
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int s[110000],t[110000],n,m; 5 int iod[110000],pstod[110000]; 6 void gtprod(int l,int r){ 7 if(l>r) return ; 8 int mx=0; 9 for(int i=l;i<=r;++i)if(pstod[s[i]]>pstod[s[mx]]) 10 mx=i; 11 printf("%c",s[mx]-1+‘A‘); 12 gtprod(l,mx-1),gtprod(mx+1,r); 13 } 14 int main(){ 15 n=0,m=0; 16 char ch=getchar(); 17 while(ch<‘A‘ || ch>‘z‘) ch=getchar(); 18 while(ch>=‘A‘ && ch<=‘Z‘){ 19 s[++n]=ch-‘A‘+1; 20 ch=getchar(); 21 } 22 while(ch<‘A‘ || ch>‘z‘) ch=getchar(); 23 while(ch>=‘A‘ && ch<=‘Z‘){ 24 t[++m]=ch-‘A‘+1; 25 ch=getchar(); 26 } 27 for(int i=1;i<=n;++i) iod[s[i]]=i; 28 for(int i=1;i<=n;++i) pstod[t[i]]=i; 29 gtprod(1,n); 30 return 0; 31 }
原文：https://www.cnblogs.com/cdcq/p/12143619.html
