Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5381 --二叉查找树
5381: 二叉查找树
警告!
题目
状态
题解
题目描述
二叉查找树是一种特殊的二叉树(每个节点最多只有两个儿子的树)。树的每个节点上存有一个唯一的值,并且满足:这个节点的左子树内所有点的值都比这个节点的值小,且右子树内所有点的值都比这个节点的值要大。 对于一棵二叉查找树T,我们可以将一个值为val的新点插入T中,且保持树的性质。算法如下: ``` //lc[x]表示节点x的左儿子 //rc[x]表示节点x的右儿子 //num[x]表示节点x的权值 void insert(int x, int val) { if (val < num[x]) { if (!lc[x]) { lc[x] = ++T; return ; } else insert(lc[x], val); } else if (val > num[x]) { if (!rc[x]) { rc[x] = ++T; return ; } else insert(rc[x], val); } } ``` 需要将 $val$ 插入二叉查找树 $T$ 时,执行 `insert(root, val)` 。 现在有 $N$ 个数需要插入一棵空树中。给定插入序列,请在每个元素被插入之后,输出所有节点的深度总和(根的深度为 $0$ )。
输入
输入的第一行一个整数 $n$,表示序列长度。 以下 $n$ 行是序列中的数字,这些数字是各不相同的,在 $[1,n]$ 区间。
输出
输出 $n$ 行,第 $i$ 行整数表示第 $i$ 个数插入树后,至这个节点的节点深度总和。
样例输入输出
输入#1
复制
8 3 5 1 6 8 7 2 4
输出#1
复制
0 1 2 4 7 11 13 15
提示
对于 $100\%$ 的数据,$N \leq 3 \times 10^5$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
点击显示
if ($pr_flag) { ?>
递交数
1
已通过
1
} ;?>
通过率
100%
时间限制
1 秒
内存限制
128 MB
来源
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和