P2273.第1题-满足查询范围的平衡树数据之和

1000ms

Difficulty: 5

所属公司 : 华为

算法与标签>递归

题目内容

数据库索引技术使用平衡树从树根到叶子节点的高度基本一致的特点，将数据保存到叶子节点，从而可以实

现从树根查找到叶子遍历的节点数基本一致，使查询速度更加稳定。

给定一个数组，经过升序排列后，构造平衡二叉树，查询平衡二叉树满足条件的叶子节点的数据之和。

平衡二叉树的定义和约束如下:

$a)$ 每个节点的左右子树的高度差的绝对值不超过 $1$

$b)$ 左右子树也是平衡二叉树

$c)$ 递增排序后构造的平衡二叉树是唯一的

第一行:一个数组，第一个数据是节点数，范围是[ $1,5000$ ]，后面跟的是树的节点值，范围是[ $1,20000$ ]。

第二行:平衡树叶子节点值的查询范围，包含 $3$ 个数，第一个数是个数，第二个数和第三个数分别是最小值和最大值。

满足查询范围的叶节点的数据之和，如果找不到满足查询条件的叶节点，则输出叶节点的最大值，其他情况返回 $-1$ 。

输入

6 7 17 35 56 65 66
2 56 67

输出

说明

叶节点的值分别是 $17\ 56\ 66$ ，满足 $>=56$ 且 $<=67$ 的是 $56\ 66$ ，所以求和是 $122$ 。

                35

            /        \

          7           65

            \       /      \

            17     56      66

输入

2 1 2100
2 1 1

输出

说明

叶子节点的值 $2100$ ，不满足查询范围 $1$ ，所以输出叶子节点最大值 $2100$ 。

输入

预期输出（选填）