蓝桥杯|历届真题:完全二叉树的权值

jupiter
2022-04-05 / 0 评论 / 561 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年04月05日,已超过745天没有更新,若内容或图片失效,请留言反馈。

1.题目

问题描述

  给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从
  上到下、从左到右的顺序依次是 A1, A2, · · · AN,如下图所示:

  现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点
  权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。
  注:根的深度是 1。

输入格式

  第一行包含一个整数 N。
  第二行包含 N 个整数 A1,
  A2, · · · AN 。

输出格式

  输出一个整数代表答案。

样例输入

7
1 6 5 4 3 2 1

样例输出

2

评测用例规模与约定

对于所有评测用例,1 ≤ N≤ 100000,−100000 ≤ Ai ≤ 100000。

2. 题解

2.1 思路分析

1.根据节点数量N求解二叉树的高度
    完全二叉树为满二叉树或者除去最后一层为满二叉树。
    高度为H的满二叉树的节点数量为2^H-1。(根节点记为第1层)
    根据这一条件即可求出N个节点对应的完全二叉树的高度treeHeight

2.求解完全二叉树最后一层节点的数量
    最后一层节点的数量为N-Math.pow(2,treeHeight-1)+1

3.按层输入每层节点的权值并计算每层的权值和

2.2 代码实现

import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int N = scanner.nextInt();

        // 求解完全二叉树高度
        int treeHeight = 0;
        int count = 1;
        while (count<N+1){
            count*=2;
            treeHeight++;
        }
        // 记录每层的权值和
        int[] weightSumArr = new int[treeHeight+1];
        Arrays.fill(weightSumArr,0);

        // 输入并求权值和
        for (int i = 1; i <treeHeight; i++) {
            for (int j = 0; j < Math.pow(2,i-1); j++) {
                weightSumArr[i] += scanner.nextInt();
            }
        }
        for (int i = 0; i < N-Math.pow(2,treeHeight-1)+1; i++) {//最后一层需要单独处理
            weightSumArr[treeHeight] += scanner.nextInt();
        }

        int maxWeightHeight = 1;
        for (int i = 2; i <= treeHeight; i++) {
            if(weightSumArr[i]>weightSumArr[maxWeightHeight]){
                maxWeightHeight = i;
            }
        }

        System.out.println(maxWeightHeight);
    }
}

2.3 提交结果

评测点序号评测结果得分CPU使用内存使用下载评测数据
1正确10.0078ms22.48MB输入 输出
2正确10.0062ms22.47MBVIP特权
3正确10.0078ms22.51MBVIP特权
4正确10.0093ms22.58MBVIP特权
5正确10.0093ms25.16MBVIP特权
6正确10.00187ms34.37MBVIP特权
7正确10.00375ms91.69MBVIP特权
8正确10.00390ms91.57MBVIP特权
9正确10.00359ms90.37MBVIP特权
10正确10.00406ms92.12MBVIP特权

参考资料

  1. http://lx.lanqiao.cn/problem.page?gpid=T2695
0

评论 (0)

打卡
取消