Codeforces Round #353 (Div. 2) D. Tree Construction(每个点按照二叉树排序树的插入插入到树中,问最后每个点的父亲节点的值是多少)

_zidaoziyan

于 2016-08-11 22:52:33 发布

阅读量375

点赞数

分类专栏： codeforces

本文链接：https://blog.csdn.net/acm_fighting/article/details/52187385

版权

codeforces 专栏收录该内容

25 篇文章

订阅专栏

本文解析了 Codeforces Round #353 (Div.2) D. Tree Construction 的解题思路，利用 set 和 map 数据结构实现二叉排序树的构造过程，并输出每个节点的父节点值。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

传送门:Codeforces Round #353 (Div. 2) D. Tree Construction

题意:每个点按照二叉树排序树的插入插入到树中,问最后每个点的父亲节点的值是多少

思路:
根据二叉排序树的性质可以知道,一个数插入到二叉排序树中,要么是插入到正好比它大的数的左边,要么是正好比它小的数的右边,利用一个set维护一下就可以了

#include<bits/stdc++.h>
using namespace std;
set<int>st;
map<int,int>ls,rs;

int main(){
    int n,x;
    scanf("%d",&n);
    scanf("%d",&x);
    st.insert(x);
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        auto it=st.lower_bound(x);
        if(it==st.end()){
            it--;
            rs[*it]=x;
            printf("%d ",*it);
        }
        else if(ls[*it]==0){
            ls[*it]=x;
            printf("%d ",*it);
        }
        else{
            it--;
            rs[*it]=x;
            printf("%d ",*it);
        }
        st.insert(x);
    }
}