Lougu P1827 American Heritage

题目

简明题意

给出一个树中序和前序遍历输出树的后续遍历

---

题解

首先会写这道题你要有一定的前置技能

• 了解树的基本知识和树的三种遍历方法
• 知道前序、中序或者知道后序、中序怎么求另一种序列
• 会编程

树的三种遍历

不做过多解释

树的中序遍历是按照左子树，根，右子树的顺序访问节点。

树的前序遍历是按照根，左子树，右子树的顺序访问节点。

树的后序遍历是按照左子树，右子树，根的顺序访问节点。

还原

这是个初赛知识，简单的说一下

首先据前序的一个结点或后序的最后一个结点这个结点是当前序列的根节点

根据当前序列的根节点在中序中把树分成左右两个子树

递推下去

如果你掌握了以上几个前置技能请继续

首先根据当前序列分出左右子树和根

1. 遍历左子树
2. 遍历右子树
3. 输出根

这点用\(DFS\)能非常简单的实现

---

coding

#include <bits/stdc++.h>
using namespace std;


string a,b;//a中序 b前序


inline void dfs(int la,int ra,int lb,int rb)
{
    if(la > ra || lb > rb) return ;
    register int i = a.find(b[lb]);
    dfs(la,i-1,lb+1,lb+i-la);//left son
    dfs(i+1,ra,lb+i-la+1,rb);//rgiht son
    cout << a[i];
}


int main()
{
    cin >> a >> b;

    int len = a.size() - 1;

    dfs(0,len,0,len);

    return 0;
}