题解 | 二叉排序树

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

struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode *parent;
    TreeNode(int c,TreeNode* p = nullptr):data(c),left(nullptr),right(nullptr),parent(p){};
};

int Insert(TreeNode* &root,int c, TreeNode* p = nullptr){
    if(root==nullptr){
        root = new TreeNode(c,p);
        if(p==nullptr) return -1;
        else return p->data;
    }
    else if(c>root->data){
        return Insert(root->right,c,root);
    }
    else if(c<root->data){
        return Insert(root->left, c,root);
    }
    return -1;
}

int main() {
    int n;
    cin>>n;
    TreeNode* root = nullptr;
    while(n>0){
        int a;
        cin>>a;
        int parent = Insert(root,a);
        cout<<parent<<endl;
        n--;
    }
    return 0;
}