题解 | #二叉排序树#递归插入加递归遍历

#include <iostream>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left = nullptr, *right = nullptr;
    TreeNode(int x) : val(x) {}
    ~TreeNode() {
        if (left) {
            delete left;
            left = nullptr;
        }
        if (right) {
            delete right;
            right = nullptr;
        }
    }
};
TreeNode *insertBST(TreeNode *root, int x) {
    if (root == nullptr) return new TreeNode(x);
    if (x < root->val) root->left = insertBST(root->left, x);
    else if (x > root->val) root->right = insertBST(root->right, x);//为了去重，不能直接写else
    return root;
}
void preOrder(TreeNode *root) {
    if (root == nullptr) return;
    cout << root->val << ' ';
    preOrder(root->left);
    preOrder(root->right);
}
void inOrder(TreeNode *root) {
    if (root == nullptr) return;
    inOrder(root->left);
    cout << root->val << ' ';
    inOrder(root->right);
}
void postOrder(TreeNode *root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << ' ';
}
int main() {
    int n;
    while (cin >> n) {
        TreeNode *root = nullptr;
        while (n--) {
            int x;
            cin >> x;
            root = insertBST(root, x);
        }
        preOrder(root);
        cout << '\n';
        inOrder(root);
        cout << '\n';
        postOrder(root);
        cout << '\n';
        delete root;
    }
    return 0;
}