输入样例
ABEDFCHG CBADEFGH输出样例
AEFDBHGC题意：根据先序序列和中序序列构造出二叉树求出后序序列。
解题思路：
首先我们知道 先序序列顺序：根->左子树->右子树 中序序列顺序：左子树->根->右子树 后序序列顺序：左子树->右子树->根
因此先序序列的第一个结点就是根节点，而根节点在中序序列中找到，左边为左子树，右边为右子树，递归进行就可以构造出整棵树
根据样例：
先序序列： C B A D E F G H 0 1 2 3 4 5 6 7 中序序列： A B E D F C H G 0 1 2 3 4 5 6 7
我们发现根节点为C，在中序序列中，0-4为左子树，6-7为右子树 而在前序序列中，如果去掉根节点，那么B从0开始，左子树就为0-4，右子树为5-6 那么我们就只需要不断递归切割序列即可
先介绍substr函数，substr只会截取子串但不会删除，字符串本身不变。
string s = "0123456789"; string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = "56789" string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = "567"完整代码，详细请看注释
#include <iostream> #include <string> #include <cstring> using namespace std; void LaterOrder(string pre,string inor) { if(pre.empty()) { return ; } char root = pre[0];//先找到根节点 int k = inor.find(root);//在中序序列中找到根节点 pre.erase(pre.begin());//删掉前序序列中根节点 string leftpre = pre.substr(0,k);//找到前序序列中左子树 string rightpre = pre.substr(k);//找到前序序列中右子树 string leftinor = inor.substr(0,k);//找到中序序列中左子树 string rightinor = inor.substr(k+1);//找到中序序列中右子树 LaterOrder(leftpre,leftinor);//递归切割左子树 LaterOrder(rightpre,rightinor);//递归切割右子树 cout << root; //由于是输出后序序列，而后序序列是左子树->右子树->根节点，所以每次都从叶结点开始输出 } int main() { string inor,pre; cin >> inor >> pre; LaterOrder(pre,inor); cout << endl; return 0; }