本文共 1999 字，大约阅读时间需要 6 分钟。

要解决给定两个深度优先搜索（DFS）序列，构造满足这两个序列的二叉树的问题，我们可以通过递归的方法结合哈希表来确定每个节点的父节点。以下是详细的步骤：

方法思路

解决代码

#include 
   
    using namespace std;#define MP make_pair#define PB push_back#define ll long long#define PII pair
    
     const int K = 1e6 + 7;const int mod = 1e9 + 7;int n, a[K], b[K], sum[K], ans[K];int ha[K], hb[K]; // 记录每个节点在b和a序列中的位置void solve(int x, int y, int fa, int sz) {    if (x > sz) return;    ans[a[x]] = ans[b[y]] = fa;    if (a[x] == b[y]) {        sum[fa]++;    } else {        sum[fa] += 2;    }    if (x == sz) return;    if (a[x] == b[y]) {        solve(x + 1, y + 1, a[x], sz);    } else {        int ta, tb;        ta = ha[b[y]] - 1;        tb = hb[a[x]] - y + ta;        if (x != ta) {            solve(x + 1, hb[a[x]] + 1, a[x], ta);        }        if (y != hb[a[x]] - 1) {            solve(ta + 2, y + 1, b[y], tb);        }        if (tb != sz) {            int fd = fa;            if (sum[fa] == 2) fd = ans[fa];            solve(tb + 1, tb - x + y + 1, fd, sz);        }    }}int main() {    ios::sync_with_stdio(false);    cin.tie(0);    int t;    while (t--) {        cin >> n;        for (int i = 1; i <= n; ++i) {            cin >> a[i];            ha[a[i]] = i;        }        for (int i = 1; i <= n; ++i) {            cin >> b[i];            hb[b[i]] = i;        }        solve(1, 1, 0, n);        for (int i = 1; i <= n; ++i) {            cout << ans[i] << " ";        }        cout << "\n";    }}
    
   

代码解释

这种方法通过递归和哈希表高效地处理构造过程，确保每个节点的位置和父节点都被正确确定，满足题目要求。