思路:递归建树 + 模拟

1. 构建平衡二叉搜索树： 1.根据题意，将输入的节点值进行升序排序。 2.使用递归的方法，选择中间元素作为当前根节点，递归构建左右子树，保证平衡。

2. 收集叶子节点： 遍历整棵树，找到所有叶子节点（左右子树均为空的节点），并将它们的值存入列表。

3. 处理查询条件：

   • 从收集到的叶子节点中，筛选出符合 min_val <= val <= max_val 的节点值。
   • 如果找到的叶子节点数量与查询的数量 q 相等，则返回这些节点的值之和。
   • 如果没有符合条件的叶子节点，则返回叶子节点中的最大值。
   • 如果符合条件的节点数量不等于 q 且不为空，则返回 -1。

代码

python

# 定义二叉树节点类
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 从排序好的列表构建平衡二叉搜索树
def build_balanced_bst(sorted_list, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    node = Node(sorted_list[mid])
    node.left = build_balanced_bst(sorted_list, start, mid - 1)
    node.right = build_balanced_bst(sorted_list, mid + 1, end)
    return node

# 收集平衡二叉树的叶子节点值
def collect_leaf_nodes(root, leaf_nodes):
    if root is None:
        return
    if root.left is None and root.right is None:
        leaf_nodes.append(root.val)
    else:
        collect_leaf_nodes(root.left, leaf_nodes)
        collect_leaf_nodes(root.right, leaf_nodes)

def main():
    # 读取第一行输入
    parts = list(map(int, input().split()))
    n = parts[0]  # 节点数量
    node_values = parts[1:]
    
    # 对节点值进行排序
    sorted_values = sorted(node_values)
    
    # 构建平衡二叉搜索树
    root = build_balanced_bst(sorted_values, 0, n - 1)
    
    # 收集所有叶子节点的值
    leaf_nodes = []
    collect_leaf_nodes(root, leaf_nodes)
    
    if not leaf_nodes:
        print(-1)
        return
    
    max_leaf = max(leaf_nodes)  # 叶子节点的最大值
    
    # 读取第二行输入
    query_parts = list(map(int, input().split()))
    
    q, min_val, max_val = query_parts[:3]  # 查询参数：期望数量，最小值，最大值
    
    # 找出满足查询范围的叶子节点
    valid_leaves = [val for val in leaf_nodes if min_val <= val <= max_val]
    
    if len(valid_leaves) == q:
        print(sum(valid_leaves))
    elif len(valid_leaves) == 0:
        print(max_leaf)
    else:
        print(-1)

if __name__ == "__main__":
    main()

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

C++

#include <bits/stdc++.h>
using namespace std;

int sumleaf = 0;  // 存储符合条件的叶子节点值的总和
int maxleaf = 0;  // 存储所有叶子节点中的最大值
int count1 = 0;   // 记录符合条件的叶子节点的数量

// 二叉树节点定义
struct TreeNode
{
    int val;  // 节点的值
    TreeNode *left;  // 左子节点
    TreeNode *right; // 右子节点

    // 构造函数，初始化节点值，并设置左右子节点为空
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 使用有序数组构建平衡二叉树
TreeNode *buildTree(vector<int> &inputs, int l, int r)
{
    // 当左索引大于右索引时，返回空，表示没有更多节点
    if (l > r)
        return nullptr;
    
    // 取中间元素作为当前节点，确保树的平衡
    int mid = (r + l) / 2;
    
    // 创建一个新节点，并递归构建其左子树和右子树
    TreeNode *root = new TreeNode(inputs[mid]);
    root->left = buildTree(inputs, l, mid - 1);  // 递归构建左子树
    root->right = buildTree(inputs, mid + 1, r); // 递归构建右子树
    
    return root;  // 返回根节点
}

// 寻找叶子节点并计算符合条件的叶子节点总和
void findLeaf(TreeNode *root, int minv, int maxv)
{
    if (root == nullptr)
        return;  // 当前节点为空，直接返回

    // 如果当前节点是叶子节点（没有左子树和右子树）
    if (root->left == nullptr && root->right == nullptr)
    {
        // 判断叶子节点的值是否在给定的范围内
        if (root->val >= minv && root->val <= maxv)
        {
            sumleaf += root->val;  // 累加符合条件的叶子节点的值
            count1++;  // 记录符合条件的叶子节点的数量
        }
    }

    // 更新所有叶子节点中的最大值
    maxleaf = max(maxleaf, root->val);
    
    // 递归搜索左子树和右子树
    findLeaf(root->left, minv, maxv);
    findLeaf(root->right, minv, maxv);
}

int main()
{
    int n;
    cin >> n;  // 输入节点的数量

    // 输入数组，存储二叉树的节点值
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];  // 逐个输入节点的值
    }

    // 输入查询范围和期望匹配的叶子节点数量
    int m, minv, maxv;
    cin >> m >> minv >> maxv;
    
    // 对数组进行排序，确保能够构建平衡二叉树
    sort(a.begin(), a.end());

    // 构建平衡二叉树
    TreeNode *root = buildTree(a, 0, n - 1);
    
    // 查找符合条件的叶子节点
    findLeaf(root, minv, maxv);
    
    // 根据符合条件的叶子节点的数量与期望的数量 `m` 进行判断
    if (m == count1)
    {
        // 如果符合条件的叶子节点数量等于 `m`，输出这些节点值的总和
        cout << sumleaf << endl;
    }
    else if (count1 == 0)
    {
        // 如果没有符合条件的叶子节点，输出所有叶子节点中的最大值
        cout << maxleaf << endl;
    }
    else
    {
        // 如果符合条件的叶子节点数量不等于 `m`，输出 -1
        cout << -1 << endl;
    }

    return 0;  // 返回程序成功运行的状态
}

java

import java.util.*;

// 二叉树节点定义
class TreeNode {
    int val;  // 节点的值
    TreeNode left;  // 左子节点
    TreeNode right; // 右子节点

    // 构造函数，初始化节点值，并设置左右子节点为空
    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

public class Main {
    static int sumleaf = 0;  // 存储符合条件的叶子节点值的总和
    static int maxleaf = 0;  // 存储所有叶子节点中的最大值
    static int count1 = 0;   // 记录符合条件的叶子节点的数量

    // 使用有序数组构建平衡二叉树
    public static TreeNode buildTree(List<Integer> inputs, int l, int r) {
        if (l > r) {
            return null;  // 当左索引大于右索引时，返回空
        }

        int mid = (r + l) / 2;  // 取中间元素作为当前节点
        TreeNode root = new TreeNode(inputs.get(mid));  // 创建新节点
        root.left = buildTree(inputs, l, mid - 1);  // 递归构建左子树
        root.right = buildTree(inputs, mid + 1, r); // 递归构建右子树
        return root;  // 返回根节点
    }

    // 寻找叶子节点并计算符合条件的叶子节点总和
    public static void findLeaf(TreeNode root, int minv, int maxv) {
        if (root == null) {
            return;  // 当前节点为空，直接返回
        }

        // 如果当前节点是叶子节点（没有左子树和右子树）
        if (root.left == null && root.right == null) {
            if (root.val >= minv && root.val <= maxv) {
                sumleaf += root.val;  // 累加符合条件的叶子节点的值
                count1++;  // 记录符合条件的叶子节点的数量
            }
        }

        maxleaf = Math.max(maxleaf, root.val);  // 更新所有叶子节点中的最大值
        findLeaf(root.left, minv, maxv);  // 递归搜索左子树
        findLeaf(root.right, minv, maxv); // 递归搜索右子树
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();  // 输入节点的数量
        List<Integer> a = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            a.add(scanner.nextInt());  // 逐个输入节点的值
        }

        int m = scanner.nextInt();  // 输入期望的叶子节点数量
        int minv = scanner.nextInt();  // 输入最小值范围
        int maxv = scanner.nextInt();  // 输入最大值范围

        Collections.sort(a);  // 对数组进行排序

        TreeNode root = buildTree(a, 0, n - 1);  // 构建平衡二叉树
        findLeaf(root, minv, maxv);  // 查找符合条件的叶子节点

        if (m == count1) {
            System.out.println(sumleaf);  // 输出符合条件叶子节点的总和
        } else if (count1 == 0) {
            System.out.println(maxleaf);  // 如果没有符合条件的叶子节点，输出最大值
        } else {
            System.out.println(-1);  // 如果符合条件叶子节点数量不等于 `m`，输出 -1
        }

        scanner.close();
    }
}

题目内容

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

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

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

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

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

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

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

输入描述

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

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

输出描述

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

样例1

输入

6 7 17 35 56 65 66
2 56 67

输出

122

说明

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

​                35

​            /        \

​          7           65

​            \       /      \

​            17     56      66

样例2

输入

2 1 2100
2 1 1		

输出

2100

说明

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

​    1

​      \

​       2100