【题解】父亲节点

题意

给你一个长度为的序列，请你构造一棵二叉排序树，从第二个数开始依次输出每个数的父亲节点。

题解

正常用递归去插入构建一棵二叉排序树，若当其为一条链时复杂度就会变为这肯定是会超时的。所以我们不能直接构建一棵二叉排序树。由于所有的数都是不同的，那么可以用和来模拟构建一棵二叉排序树。对于每次输入的数，我们用中的来找到第一个比输入值大的数，如果找到了且该点的左儿子不存在，就把其插入中该节点的左儿子，若没找到，若没找到，或者左子树已经存在了，那么我们就去找小于这个数最大的数。将输入的数作为其右儿子。

复杂度

时间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
map<int,int> Left,Right;
set<int> tree;
set<int>::iterator it;
int main()
{
    int n,x,ret;
    scanf("%d",&n);
    scanf("%d",&x);
    tree.insert(x);
    for(int i=1; i<n; i++)
    {
        scanf("%d",&x);
        it = tree.upper_bound(x);
        if(it != tree.end() && Left.count(*it) == 0)
        {
            Left[*it] = x;
            ret = *it;
        }
        else
        {
            it--;
            Right[*it] = x;
            ret = *it;
        }
        tree.insert(x);
        printf("%d ",ret);
    }
    return 0;
}