#include <bits/stdc++.h>
using namespace std;
int a1[100005], a2[100005];
// 中序遍历区间 [x1, y1],后序遍历区间 [x2, y2]
void dfs(int x1, int y1, int x2, int y2) {
if (x1 > y1 || x2 > y2) return; // 区间为空时返回
int root = a2[y2]; // 后序遍历的最后一个元素是根节点
cout << root << ' '; // 输出根节点(先序遍历:根->左->右)
// 在中序遍历中找到根节点的位置
int k = x1;
while (k <= y1 && a1[k] != root) k++;
int left_size = k - x1; // 左子树的节点数量
// 递归处理左子树
dfs(x1, k - 1, x2, x2 + left_size - 1);
// 递归处理右子树
dfs(k + 1, y1, x2 + left_size, y2 - 1);
}
int main() {
string s1, s2;
getline(cin, s1);
getline(cin, s2);
int ans = 0, k = 0;
// 解析中序遍历序列
for (int i = 0; i < s1.size(); i++) {
if (s1[i] == ' ') {
a1[k++] = ans;
ans = 0;
continue;
}
ans = ans * 10 + (s1[i] - '0');
}
a1[k++] = ans;
ans = 0, k = 0;
// 解析后序遍历序列
for (int i = 0; i < s2.size(); i++) {
if (s2[i] == ' ') {
a2[k++] = ans;
ans = 0;
continue;
}
ans = ans * 10 + (s2[i] - '0');
}
a2[k++] = ans;
dfs(0, k - 1, 0, k - 1);
return 0;
}
共 2 条回复
好的,我再看看
数据应该是没问题的 我看站长也验过一次