M01577: Falling Leaves

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

#include <bits/stdc++.h>

using namespace std;

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

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
using vi = vector<int>;
using usi = 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;
}

class Tree {
    struct Node {
        int val;
        Node *lson, *rson;
        Node() {
            val = -1;
            lson = nullptr, rson = nullptr;
        }
        Node(int x) {
            val = x;
            lson = nullptr, rson = nullptr;
        }
    };
    Node *root;

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

  public:
    Tree(char ch) { root = new Node(ch - 'A'); }
    void insert(char ch) {
        int val = ch - 'A';
        Node *cur = root;
        while (cur) {
            if (val > cur->val) {
                if (cur->rson)
                    cur = cur->rson;
                else {
                    cur->rson = new Node(val);
                    break;
                }
            } else {
                if (cur->lson)
                    cur = cur->lson;
                else {
                    cur->lson = new Node(val);
                    break;
                }
            }
        }
    }
    void traverse() { traverse(root); }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    bool is_end = false;
    while (!is_end) {
        string str;
        vector<string> v;
        while (getline(cin, str)) {
            if (str == "*")
                break;
            if (str == "$") {
                is_end = true;
                break;
            }
            v.push_back(str);
        }
        reverse(all(v));
        Tree t(v[0][0]);
        for (int i = 1; i < sz(v); i++) {
            for (char ch : v[i]) {
                t.insert(ch);
            }
        }
        t.traverse();
        cout << '\n';
    }
    return 0;
}