P1827 [USACO3.4] 美国血统 American Heritage 洛谷

题目链接：/problem/P5076、

思路：

递归 （具体以后再补充）

见代码有注释，希望注释有用......

代码如下：

#include<iostream>#include<string>using namespace std;string pre, inor;void tree(string pre, string inor){if (pre.empty()) //空则返回{return;}char root = pre[0]; //先序中第一个结点一定是根节点int k = inor.find(root); //在中序中查找根结点的位置pre.erase( pre.begin ( ) );//删除根结点，后续寻找新的根结点string leftpre, rightpre, leftinor, rightinor;//不能进行全局声明，不然会超时leftpre = pre.substr(0, k);//截取左子树的先序列leftinor = inor.substr(0, k); //截取左子树的中序列rightpre = pre.substr(k); //截取右子树的先序列rightinor = inor.substr(++k); //截取右子树的中序列tree(leftpre, leftinor); //遍历左子树tree(rightpre, rightinor);//遍历右子树cout << root; }int main(){cin >> inor >> pre;tree(pre, inor);return 0;}

欢迎路过的大佬能指出不足 ^-^