描述
输入某二叉树的后序遍历和中序遍历的结果，请输出前序遍历序列。假设输入的后序遍历和中序遍历的结果中都不含重复的数字。例如输入后序遍历序列{7,1,4,2,5,8,6,3,1}和中序遍历序列{4,7,2,1,5,3,8,6}，重建二叉树并返回后序遍历序列
输入
输入某二叉树的后序遍历和中序遍历的结果
输出
输出前序遍历序列
输入样例 1
7 4 2 5 8 6 3 1
4 7 2 1 5 3 8 6
输出样例 1
1 2 4 7 3 5 6 8
参考题目详解：已知前序遍历和中序遍历求二叉树
实现代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node* BinTree;
struct node{int date;BinTree left;BinTree right;
};
BinTree Build(int post[] ,int in[],int size)
{if(size<=0)return NULL;//先在中序中找到根节点int i=0;for(i=0;i<size;i++){if(in[i]==post[size-1])break;} BinTree tree=(BinTree)malloc(sizeof(struct node));tree->date=post[size-1];tree->left=Build(post,in,i);tree->right=Build(post+i,in+i+1,size-1-i);return tree;
}void preorder(BinTree T) //前序遍历
{if(T==NULL)return;else{printf("%d ",T->date);preorder(T->left);preorder(T->right);}}
int main()
{char postt[800],inn[800]; gets(postt);gets(inn); int size=strlen(postt); int post[800],in[800];int postcount=0; int i;for(i=0;i<size;i++){if(i==0){post[postcount]=postt[i]-'0';}else{if(postt[i]>='0'&&postt[i]<='9'){//此if-else 用来转换多位数为int类型 if(postt[i-1]==' ') //如果前一个元素为空格 {postcount++;post[postcount]=postt[i]-'0';}else //如果前一个元素不是空格，那么说明与前一个元素一同构成的数 例如：10 {post[postcount]=post[postcount]*10+(postt[i]-'0');}}}}int incount=0;for(i=0;i<size;i++){if(i==0){in[incount]=inn[i]-'0'; }else{if(inn[i]>='0'&&inn[i]<='9'){if(inn[i-1]==' '){incount++;in[incount]=inn[i]-'0';}else{in[incount]=in[incount]*10+(inn[i]-'0');}}}} //如果后序遍历的结点数与中序遍历的结点数相同且不为0，那么可以找到对应二叉树 if(postcount==incount&&postcount!=0) {BinTree T;T=Build(post,in,postcount+1);preorder(T);}return 0;}