根据二叉树先序和中序遍历得出后序遍历

思路：

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;
}