本文共 1999 字，大约阅读时间需要 6 分钟。
要解决给定两个深度优先搜索（DFS）序列，构造满足这两个序列的二叉树的问题，我们可以通过递归的方法结合哈希表来确定每个节点的父节点。以下是详细的步骤：
方法思路
问题分析：
- 两个DFS序列分别为a和b，要求构造一个二叉树，使得它的前序遍历结果分别为a和b。
- 根据DFS的特性，根节点先被访问，然后是左子树，接着是右子树。
关键观察：
- 对于相同的节点，可能是同一个节点的左或右子节点。
- 对于不同的节点，可能分别作为左子节点和右子节点。
递归策略：
- 使用递归函数，分别处理a和b序列的当前位置。
- 当a和b序列中的节点相同时，确定为同一父节点的左或右子节点。
- 当节点不同时，分别处理它们作为父节点的左和右子节点。
哈希表辅助：
- 建立哈希表记录每个节点在序列a和b中的位置。
- 通过这些表快速定位节点的位置，避免重复计算和错误处理。
递归函数实现：
- 函数参数包括当前处理的位置和父节点。
- 递归终止条件：当前位置超过处理范围。
- 处理当前节点，设置父节点。
- 根据节点是否相同，分别处理左或右子节点。
解决代码
#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"; }}
代码解释
输入处理：
- 读取输入数据，建立哈希表记录每个节点在序列a和b中的位置。
递归函数solve：
- 处理当前位置x和y，以及父节点fa和范围sz。
- 记录当前节点的父节点。
- 根据节点是否相同，决定处理方式：相同则为单子节点，不同则分别处理左和右子节点。
构造父节点数组：
这种方法通过递归和哈希表高效地处理构造过程，确保每个节点的位置和父节点都被正确确定，满足题目要求。
转载地址：http://kprfk.baihongyu.com/