题解 | #二叉排序树#

#include <iostream>
using namespace std;

int n;

struct TreeNode{
    long long data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(long long val): data(val){};
};

void insertTree(TreeNode* node, TreeNode* root){
    if(root == NULL) return; //如果当前比较结点为空 则返回空
    if(root->left == NULL && root->data > node->data){ //只有在当前结点的左节点为空 且大小关系符号时 插入
        root->left = node;
        cout << root->data << endl;
        return ;
    }
    if(root->right == NULL && root->data <= node->data){ //只有在当前结点的左节点为空 且大小关系符号时 插入
        root->right = node;
         cout << root->data << endl;
        return ;
    }
    if(root->data > node->data) insertTree(node, root->left); //左子树递归
    else insertTree(node, root->right); //右子树递归
}

int main() {
    
    while (cin >> n) { // 注意 while 处理多个 case
        if(n == 0 || n == 1) {
            cout << -1 << endl;
            continue;
        }
        long long data;
        cin >> data;
        TreeNode* root = new TreeNode(data); 
        cout << -1 << endl;
        for(int i = 1; i < n; i++){
            long long data;
            cin >> data;
            TreeNode* node = new TreeNode(data); 
            insertTree(node, root);
        }

    }
}
// 64 位输出请用 printf("%lld")