思路：
pre:前序遍历序列；in:中序遍历序列每次取先序序列的首字符即为当前子树的根结点，在中序序列中找到该字符的对应位置index。
在先序序列中该结点的左子树包含结点的下标对应是1~index，右子树包含结点的下标对应是index+1~字符串尾。
在中序序列中该结点的左子树包含结点的下标对应是0~index-1，右子树包含结点的下标对应是index+1~字符串尾。
递归下去
代码
#include<iostream>
#include<string>
using namespace std;
struct node {
node *left, *right;
char val;
};
node *createTree(string pre, string in)
{
node *t = nullptr;
if(pre.length() > 0) {
t = new node;
t -> val = pre[0];
int index = in.find(pre[0]);
t -> left = createTree(pre.substr(1, index), in.substr(0, index));
t -> right = createTree(pre.substr(index + 1), in.substr(index + 1));
}
return t;
}
void post_order(node *root)
{
if(root != nullptr) {
post_order(root -> left);
post_order(root -> right);
cout << root -> val;
}
}
int main()
{
string qx, zx;
while(cin >> qx >> zx) {
node *root = createTree(qx, zx);
post_order(root);
cout << endl;
}
return 0;
}
