首先本道题是我期待已久的题目了，因为总是能看到二叉树的解题方法，而且dfs实际上也是树的遍历的一种。因此这道题我想了很久，也看到了优秀的题解，首先看这个题目洛谷p1030? ??P1030 [NOIP2001 普及组] 求先序排列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题牵扯到的知识点很多，其中包括
1.二叉树的前中后序到底是什么。
2.递归函数中两次调用自身函数是如何进行的
3.c++中find函数的使用
4.还有就是substr函数的用法和注意事项。
首先，我们分析二叉树的前中后排序
以一个简单的图为例子，看下图
?前序排列就是A-B-C-D-E-G-F,简单的记住就是根节点，左子树，右子树
可以用T,LR分别表示根节点和左右节点，每次都是根节点左右节点这样遍历，一层一层的分析。
看到这里不太懂往下看，我在分析第2个问题的时候会再讲解
中序排列就是C-B-D-A-G-C-F? ?简单的记住就是左子树，根节点，右子树
后序排列就是C-D-B-G-F-E-A? ?简单的记住就是左子树，右子树，根节点
但是给出二叉树后到底是如何去遍历整棵树也就是寻找前排序的呢
可以发现，后排序的最后就是根节点，那就好办，利用中序就可以将它分割成两部分也就是左子树和右子树（C-D-B和G-C-F）,然后我们用递归分别遍历左右树就可以找到了。
然后是第二个问题，也是我最近见到的比较多的问题，比较难理解
到底在递归函数里面两次调用递归函数怎么进行的呢，这里有一个文章但是我感觉讲的有点乱，但是能够真实反映出到底是如何操作的。两次在内部调用自身的递归_??等风来的博客-CSDN博客
其实两次调用是二叉树的一个反映，差不太多，如果是是遍历二叉树的话，可以先看以下b站的这个视频数据结构与算法基础--第08周01--5.5遍历二叉树和线索二叉树3--二叉树的先序递归遍历算法_哔哩哔哩_bilibili
主要的两张图片可以反映出来思想。
??
理解其他题目的时候可以模仿性的理解，然后就不难发现原来是一个函数先进行到底，然后返回再接着去遍历另外一个同样的函数。
理解了这个之后再看第三个问题，就是find函数的使用。
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
string s, ss;
cin>>s>>ss;
int a = s.find(ss);//在s中找ss
cout<<a;
}这个是在s中寻找ss字符串，如果找不到的话a就是-1，如果可以找到a就是从0开始ss的位置，不理解的话输入例子试一下，假设s是abcdef而ss为c，测试结果如下：
abcd c
2
说明ss在s的第三个位置，但是因为从零开始所以是2.
第二个举例：
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
string s, ss;
cin >> s >> ss;
int a = s.find(ss, 1);
cout << a;
return 0;
}
输出结果为2，意思就是从指定位置开始找。常用就这些了，以后用到更多再补充吧。
最后就是substr函数的使用
之前记录过但是难免会忘记。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
string s;
int main()
{
cin >> s;
int k = s.find('d');
cout << k;
string ss,sc;
sc = s.substr(0,k);
ss=s.substr(k+1);
cout << sc<<" "<<ss;
return 0;
}输出结果
abcdef
3abc ef首先输入abcdef可以发现k是3，sc是abc说明是从零开始的3个字符，ss是ef说明是从k+1到最后的字符。
用法目前就这两个可以用到，再遇到再总结。
最后回到刚开始的时候那道题，直接上题解。
#include<iostream>
#include<cstring>
using namespace std;
string in, after;
void digui(string in, string after)
{
if(in.size() > 0)
{
char ch = after[after.size() - 1];//根据后排序确定根节点
cout << ch;//输出节点
int k = in.find(ch);//将中排序分割成左右子树
digui(in.substr(0, k), after.substr(0, k));//遍历左子树
digui(in.substr(k+1), after.substr(k,in.size()-k-1));//遍历右子树
}
}
int main()
{
cin >> in >> after;
digui(in, after);
cout << endl;
return 0;
}
本题已经在洛谷上通过。
这是一下午加晚上一个小时的结果啊。