L2-006 树的遍历(中后序确定二叉树＆层序遍历)

 代码实现：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5+10;

int n, cnt;
int bk[N], md[N];
map<int, int> pos;

struct node{
    int lson, rson, val;
}tree[N];

int build(int la, int lb, int ra, int rb){
    int root = bk[rb];
    int k = pos[root]; // 找到根节点在中序遍历中的index
    if(la < k) tree[root].lson = build(la, k-1, ra, ra+k-la-1);  // 递归左子树
    if(lb > k) tree[root].rson = build(k+1, lb, ra+k-la, rb-1);  // 递归右子树
    return root;
}

void bfs(int root){
    queue<int> q;
    vector<int> ans;
    q.push(root);
    while(q.size()){
        int t = q.front(); q.pop();
        ans.push_back(t);
        if(tree[t].lson) q.push(tree[t].lson);
        if(tree[t].rson) q.push(tree[t].rson);
    }
    cout << ans[0];
    for(int i = 1; i < ans.size(); i++) cout << " " << ans[i];
    cout << endl;
}

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> bk[i];
    for(int i = 1; i <= n; i ++){
        cin >> md[i];
        pos[md[i]] = i;
    }

    int root = build(1, n, 1, n);

    bfs(root);

    return 0;
}