递归建树，先序中第一个字符是树根，随后在中序中找到位置pos，preorder中从1长度为pos的是左子树，inorder从0开始长度为pos的就是左子树长度；类似地，preorder从pos+1一直到末尾是右子树长度，inorder从pos+1到末尾是右子树先序；

尤其注意return与=指针赋值的作用，当不断分割直到字符串为空是时，此时return NULL，返回时正好赋值给外面的newnode->left或newnode->right，这样就正确初始化了叶子结点，同时，结点左右孩子建立好后在最后返回pNewNode也正好通过指针赋值初始化为了父节点的左右孩子，一棵树从叶结点到根结点慢慢建立起来

下面是一个简单的递归运行的例子，preorder是ABC，inorder是BAC

#include <cstdio>
#include <string>
using namespace std;

struct TreeNode {
    char data;
    TreeNode* lchild, *rchild;
};

// rebuild的返回值表示子树根结点的地址
TreeNode* rebuild(string preOrder, string inOrder) {
    if (preOrder.size() == 0) {
        return NULL; // 插入叶子结点
    }
    else { // 插入非叶子，需要申请空间并递归建立它的左右子树
        // 先序序列中第一个字符就是根
        char rootdata = preOrder[0];
        // 为树根创建新结点
        TreeNode* pNewNode = new TreeNode;
        pNewNode->data = rootdata;
        // 拿到树根在中序序列中的下标，正好也是左子树的长度
        int pos = inOrder.find(rootdata);
        // 再返回到先序中，在同样长度的子串中再确定子树根结点，再到中序序列中去分割，如此循环往复，直到只有一个结点
        pNewNode->lchild = rebuild(preOrder.substr(1, pos), inOrder.substr(0, pos));
        pNewNode->rchild = rebuild(preOrder.substr(pos + 1), inOrder.substr(pos + 1));
        // 返回整棵树的根，其他递归函数中没有修改，仅在本函数中有效
        return pNewNode; // 返回子树的根，最后返回整棵树的根
    }
}

void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->lchild);
    postOrder(root->rchild);
    printf("%c", root->data);
}

// 根据先序遍历与中序遍历重建树并输出后序遍历序列
int main() {
    char preOrder[20], inOrder[30];
    while (scanf("%s%s", preOrder, inOrder) != EOF) {
        TreeNode* root = rebuild(preOrder, inOrder);
        postOrder(root);
        printf("\n");
    }
    return 0;
}