M22158:根据二叉树前中序序列建树

tree, http://cs101.openjudge.cn/practice/22158/

#include <bits/stdc++.h>

#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = std::pair<int, int>;
using vi = std::vector<int>;
using usi = std::unordered_set<int>;

int read() {
    int x = 0, f = 1;
    char ch = getchar_unlocked();
    while (!isdigit(ch)) {
        if (ch == '-')
            f *= -1;
        ch = getchar_unlocked();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar_unlocked();
    }
    return x * f;
}

struct Node {
    char val;
    Node *lson, *rson;
    Node() : val(0), lson(nullptr), rson(nullptr) {}
    Node(char ch) : val(ch), lson(nullptr), rson(nullptr) {}
};

Node *build(const string &s, const string &t, int sl, int sr, int tl, int tr) {
    if (sl > sr || tl > tr) {
        return nullptr;
    }
    if (sl == sr) {
        return new Node(s[sl]);
    }
    Node *ret = new Node(s[sl]);
    size_t pos = t.find(s[sl], tl);
    int len = pos - tl;
    ret->lson = build(s, t, sl + 1, sl + len, tl, tl + len - 1);
    ret->rson = build(s, t, sl + len + 1, sr, tl + len + 1, tr);
    return ret;
}

void traverse(Node *cur) {
    if (!cur)
        return;
    traverse(cur->lson);
    traverse(cur->rson);
    cout << cur->val;
}

int main() {
    string s, t;
    while (cin >> s >> t) {
        int n = sz(s);
        auto ret = build(s, t, 0, n - 1, 0, n - 1);
        traverse(ret);
        cout << '\n';
    }
    return 0;
}