Description二叉树的三种遍历都可以通过递归实现。 如果我们知道一棵二叉树的先序和中序序列，可以用递归的方法求后序遍历序列。输入格式两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。 树的结点一律用小写字母表示,且字符串长度不超过30。输出格式一个字符串，树的后序序列。输入样例abcde bcade输出样例cbeda
首先，我们需要掌握根据先序和中序序列来手写树的能力。以题目所给输入样例为例
已知先序序列abcde和中序序列bcade
先序序列是先根再左再右，那么我们可以知道这棵树的根结点为a。
而中序序列是先左再根再右，我们已经知道a是根结点，那么在中序序列中，a的左边bc是a的左子树（我们先不管bc的顺序），a的右边de是a的右子树（同样，我们先不管de的顺序）
再回到先序序列，找到bc，第一个是b，而在中序里对应的b的右边是c，即c是b的右孩子
再在先序中找到de，第一个是d，而在中序里对应的d的右边是e，即e是d的右孩子
这棵树就长这样啦
可能这个树比较小，大家还看不出什么规律，感兴趣的可以自己多试几个样例。
运用递归的思想，先把这棵树以a为根，分成左右两棵子树bc和de，再以b为根，又分成两棵子树……直到到了叶子结点，不能再分子树了。
可能这么说还是很抽象，看看代码就好啦。
#include#include #include #include using namespace std; void Traverse(string pre,string in) { if(pre==" " || in==" ") return; int pos=in.find(pre[0]);//根据先序找到根结点在中序的位置 Traverse(pre.substr(1,pos),in.substr(0,pos));//左子树 Traverse(pre.substr(pos+1),in.substr(pos+1));//右子树 cout< > pre >> in; Traverse(pre,in); return 0; }这个string类中的find()函数和substr()函数要是不懂的话可以去看看大佬写的解析，写的是真不错啊，第一次接触这类函数居然很容易就弄明白了，如下：
C++String中的find用法_帅帅气气的黑猫警长的博客-CSDN博客_c++ find string
C++string类中substr()函数的使用方法_&Mr.Gong的博客-CSDN博客_c++ string substr
