/*根据二叉树的后序序列和中序序列建立该二叉树。这个过程是
*一个递归过程，其基本思想是：先根据后序序列的最后一个元素建立
*根节点，然后在中序序列中找到该元素，确定根节点的左、右子树的中序序列；
*再在后序序列中确定左、右子树的后序序列；最后由左子树的后序序列与中序序列
*建立左子树，由右子树的后序序列与中序序列建立右子树。
*/
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
using namespace std;
string post, pin; //后序和中序序列（声明C++字符串）
typedef struct node
{ //树的节点
char data;
struct node *lchild;
struct node *rchild;
} BiNode,*BiTree;
int find(char c, string pin, int pos) //查找根节点在中序序列中的位置
{
for(int i=pos; pin[i]!='\0'; i++)
{
if(c==pin[i]) return i;
}
return -1;
}
//由后序和中序构造二叉树
void create(BiTree &root, int i1, int i2, int length)
{ /*i1为后序序列最后一个元素下标,i2为中序序列起始下标，
length为序列长度*/
if(length<=0)
root=NULL;
else
{
root = new BiNode;
root->data = post[i1]; //根节点为后序序列中最后一个元素
int pos = find(post[i1],pin,i2); //查找根节点在中序序列中的位置
int leftlen = pos-i2; //左子树的长度
int rightlen = length-(leftlen+1); //右子树的长度
create(root->lchild, i1-1-rightlen, i2, leftlen); //递归建立左子树
create(root->rchild, i1-1, pos+1, rightlen); //递归建立右子树
}
}
void preOrder(BiTree T) //先序遍历二叉树
{
if(T==NULL)
return;
else
{
cout<<T->data;
preOrder(T->lchild);
preOrder(T->rchild);
}
}
int main()
{
cin>>post>>pin;
BiTree T;
create(T,post.length()-1,0,post.length());
preOrder(T);
return 0;
}
