Codeforces Round #353 (Div. 2) D. Tree Construction __ Binary Search Tree

Source

D. Tree Construction

My Solution

这个 construct the binary search tree 是按照输入顺序构造的，每次从根部遍历按照二叉搜索树原理去找值然后把节点加上去

traverse the tree starting from the root 当时查单词的时候 traverse
只看到了"旋转" 然后就懵了，结果还有遍历的意思，而且根据句子翻译也是遍历 (┬＿┬) 这里不用rotate()旋转

看了题解才注意到这个，然后才搞明白 ^_^

所以每次插入，只要考虑已经出现(在树上)的比它大而且在隔壁iter，比它小而且在隔壁--iter，的两个位置

这时--iter 可能是iter的左节点或者 iter是--iter的右节点这2种情况之一，

所以先判断，iter左节点是否有值 //先判断--iter的右边是否有值也可以，效果一样。反正2种情况中的一种

如果没有值就放上去

如果有值就插在--iter的右边

#include 
#include 
#include 
#include 


using namespace std;

set valset;
map<int, int> L, R;                //这里数字比较离散，用map好，而且数组好像也开不下


int main()
{
    int n, val;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &val);
        if(i == 0) valset.insert(val);
        else{
            auto iter = valset.lower_bound(val);    //返回， 一个迭代器， 这里插入val， 顺序不变(比它大的那些往后推)
            if(iter == valset.end()) R[*(--iter)] = val;
            else{
                if(!L[*iter]) L[*iter] = val;      //优先作为比它大的且相邻的数的左子节点
                else R[*(--iter)] = val;             //如果什么的左节点非空，说明这个点比val小且相邻的点连在L[*iter] 上了
            }
            if(i == 1)printf("%d", *iter);
            else printf(" %d", *iter);
            valset.insert(val);
        }
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

Codeforces Round #353 (Div. 2) D. Tree Construction __ Binary Search Tree

相关推荐

HDU – 4355 Party All the Time 三分

Codeforces Round #403 (Div. 2) B. The Meeting Place Cannot Be Changed 三分

Codeforces Round #377 (Div. 2) D. Exams 二分+贪心 or 纯贪心水过

Codeforces Round #402 (Div. 2) D. String Game 二分+优先队列+字符串匹配

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类