题解 | #二叉排序树#

输出的时候记录一下插入节点的父结点就可以了

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    TreeNode* left;
    TreeNode* right;
    int val; 
    TreeNode(int _val) : val(_val), left(NULL), right(NULL) { }
};

TreeNode* result = NULL;

TreeNode* createBinaryTree(TreeNode* root, TreeNode* par, int data) {
    if (root == NULL) {
        result = par;
        TreeNode* node = new TreeNode(data);
        return node;
    }
    if (data < root->val) {
        root->left = createBinaryTree(root->left, root, data);
    }
    else {
        root->right = createBinaryTree(root->right, root, data);
    }
    return root;
} 

int main() 
{
    int N;
    while (cin >> N) {
        int data;
        TreeNode* root = NULL;
        while (N--) {
            cin >> data;
            root = createBinaryTree(root, NULL, data);
            if (result == NULL) cout << "-1" << endl;
            else cout << result->val << endl;
        }
    }
    return 0;
}