P1497 树的遍历

1. 树的遍历性问题，唯一难点是：得到左。有子树的对应的范围区间；当得到了左右子树的区间后，无脑递归结束；
2. 由于这里还涉及到前序、后序序列，所以左右子树的范围在2个序列中都要表示出来，因此指针数量*2；
   在2个序列中分别表示出当前树的范围（即区间的范围）即可。

算法1 (DFS建树、BFS搜索层序遍历) $O(n)$

$O(n)$

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 50;
int n;
int a[N], b[N];
int ltree[N], rtree[N];

//这类问题的关键都是找到当前序列的左子树范围序列，右子树范围序列，无脑递归就行了
int dfs(int pl, int pr, int ll, int lr)    //四个参数表达了中序、后续序列的范围
{
    int root = a[lr];
    // cout << pl << ' ' << pr << ' ' <<  root << endl;
    if(pl > pr || ll > lr) return 0;
    int mid = 0;
    for(int i = pl; i<=pr; ++i){   //在中序序列中找根结点
        if(b[i] == root){
            mid = i;
            break;
        }
    }
    //用长度+起点的的方式获取子问题的后序序列。。。
    //洛谷中本题用的是string类直接记录前序序列、后序序列，那么就可以只用长度，省略起点
    ltree[root] = dfs(pl,mid-1,ll,ll+mid-pl-1);    //这里用长度获得左子树的后续遍历序列
    rtree[root] = dfs(mid+1,pr,ll+mid-pl-1+1,lr-1);  //这里右子树的后续遍历序列就是上一步的值+1
    return root;
}

void bfs(int u)
{
    queue<int> q;
    q.push(u);
    cout << u;
    while(q.size()){
        int t = q.front();
        if(t != u) printf(" %d", t);
        q.pop();
        if(ltree[t]) q.push(ltree[t]);
        if(rtree[t]) q.push(rtree[t]);
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i<n; ++i) cin >> a[i];    //后续遍历序列
    for(int i = 0; i<n; ++i) cin >> b[i];    //中序遍历序列
    bfs(dfs(0,n-1,0,n-1));
    return 0;
}

算法2 (DFS建树、map存二叉树) $O(n)$

1. 注意到这是一颗二叉树，所以可以直接用下标关系把结点存在map中, 省去BFS的过程。但要注意题目并没有说这不是完全二叉树，所以必须用map存树上结点对应的元素，因为有些结点会是空结点，用数组会打印出0.用map没插入的元素不会打印出来。
2. 提起用hash表记录中序序列中各个元素的位置，这样后序在中序序列中查询根结点的时间：$O(1)$

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <map>
using namespace std;
const int N = 50;
int n;
int a[N], b[N];
map<int,int> ans;
unordered_map<int,int> pos;

void dfs(int pl, int pr, int ll, int lr, int id)   
{
    int root = a[lr];
    if(pl > pr) return ;
    int mid = pos[root];
    ans[id] = root;
    dfs(pl,mid-1,ll,ll+mid-pl-1, id*2);     //长度是: mid-pl; 后序起点:ll, 所以终点是:ll+mid-pl-1;
    dfs(mid+1,pr,ll+mid-pl-1+1,lr-1, id*2+1); 

}


int main()
{
    cin >> n;
    for(int i = 0; i<n; ++i) cin >> a[i];    //后续遍历序列
    for(int i = 0; i<n; ++i){
        cin >> b[i];    //中序遍历序列
        pos[b[i]] = i;
    } 
    dfs(0,n-1,0,n-1,1);
    for(auto v : ans) cout << v.second << ' ';
    return 0;
}