P1827

P1827 奶牛

题目解读

其实说到底就是一道树的后序遍历反推而已嘛
首先，让我们看一遍题目：
给了一棵树的前序中序遍历，让求出后序遍历；（习惯性的打出分号
https://oi-wiki.org/graph/tree-basic/#_14（附上OI-WIKI的讲解
首先我们知道前序遍历在开头是根节点，那么，就将根节点取出（用 string 可做到
那么，在中序遍历中找到根节点的位置，左边就是左子树，右边就是右子树
在左子树中，前序遍历的左半截的开头就是左子树的根节点，再将根节点取出，再在中序遍历的左半边寻找……
然后再在右子树中重新做一遍这个过程，（注意）重新做的时候也要从左子树开始做
！！！这是什么！！！
赤裸裸的递归啊
所以！就可以用一个递归小函数来解决这个问题

另一件事情

在上述说明中呢，看上去非常的简单；
但是，上面提到了前序遍历的左半边，难道是说要在存一个 string 做吗；
是的，需要————
但是不要惊慌
接下来我要说的就是 string 的库函数之一：substr()；
substr(本质上是复制字符串的一部分放入新的字符串之中；
就省得孩子们一遍遍的 for 了

上代码

#include<bits/stdc++.h>
using namespace std;
#define N 10010
string a,b;
void dfs(string aa,string bb)
{
    if(aa.empty())return;       //这是在判断边界
    char root=aa[0];        //将前序遍历的根节点取出来
    int k=bb.find(root);        //找到根节点
    aa.erase(aa.begin());       //将根节点从string中删除
    string laa=aa.substr(0,k),raa=aa.substr(k),lbb=bb.substr(0,k),rbb=bb.substr(k+1);       //激动人心的拆卸时间
    dfs(laa,lbb);dfs(raa,rbb);      //遍历
    cout<<root；         //由于是后序遍历所以最后输出根节点
}
int main()
{
    cin>>a>>b;
    dfs(b,a);
    cout<<endl;
    return 0;
}

尾声

森森的第一篇学术博客结束