题解 | 二叉排序树

#include <iostream>
using namespace std;
struct Node {
    int val;
    Node* l, *r;
};
void insert(Node* root, int x) {
    if (x > root->val) {
        if (root->r == nullptr) {
            Node* t = new Node;
            root->r = t;
            t->l = t->r = nullptr;
            t->val = x;
            cout << root->val << endl;
        } else {
            insert(root->r, x);
        }
    } else {
        if (root->l == nullptr) {
            Node* t = new Node;
            root->l = t;
            t->l = t->r = nullptr;
            t->val = x;
            cout << root->val << endl;
        } else {
            insert(root->l, x);
        }
    }
}
int main() {
    int n;
    int t;
    while (cin >> n) { // 注意 while 处理多个 case
        Node* root = nullptr;
        for (int i = 0; i < n; ++i) {
            cin >> t;
            if (root == nullptr) {
                root = new Node;
                root->val = t;
                root->l = root->r = nullptr;
                cout << -1 << endl;
                continue;
            }
            insert(root, t);
        }
    }
}
// 64 位输出请用 printf("%lld")

拿下