题解 | #[NOIP2001]求先序排列#

#include <bits/stdc++.h> using namespace std;

string s1, s2; // s1是中序，s2是后序

void solve(int l1, int r1, int l2, int r2) { if (l1 > r1) return;

// 后序的最后一个字符是根
char root = s2[r2];
cout << root;

// 在中序中找到根的位置
int pos = -1;
for (int i = l1; i <= r1; i++) {
    if (s1[i] == root) {
        pos = i; 
        break;
    }
}

// 左子树节点数
int leftSize = pos - l1;

// 递归遍历左子树
solve(l1, pos - 1, l2, l2 + leftSize - 1);

// 递归遍历右子树
solve(pos + 1, r1, l2 + leftSize, r2 - 1);

}

int main() { cin >> s1 >> s2; int n = s1.length(); solve(0, n - 1, 0, n - 1); return 0; }//这其实是写给未来的我的，这个目前还不是很懂，第一天学，不喜勿怪谢谢谢谢！