我这样写的在东方博弈通过,在这里没办法通过

lixiaohuan 2025-06-19 19:24:45 3

#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;

}

{{ vote && vote.total.up }}

共 2 条回复

lixiaohuan

好的,我再看看

Wind_Rises 砂糖老师

数据应该是没问题的 我看站长也验过一次