完全二叉树的权值(蓝桥杯2019年试题G)

       给定一棵包含N个节点的完全二叉树，树上的每个节点都有一个权值，按从上到小、从左到右的顺序依次是A1、A2……An,（1，2，n为下标。）如下图所示。

       现在，小明要把相同深度的节点的权值加到一起，他想知道哪深度的节点权值之和最大。如果有多个深度的权值和同为最大，则输出其中最小的深度。

      注意：根的深度是1。

     【输入格式】

       第一行包含一个整数N。

       第二行包含N个整数A1,A2,……An。  （1，2，n为下标。）

    【输出格式】

     输出一个整数，代表答案

    【样例输入】

      7

      1   6     5   4    3    2    1

    【样例输出】

      2

     【评测用例规模与约定】

       对于所有评测用例， N >= 1 && N <= 100000，   Ai(i为下标)>=-100000&&<=100000。

     【解析】

        本题并无特殊技巧，对每一层进行遍历并算出每层的权值，最后比较出最大值即可。需要注意二叉树的存储和数组下标的关系，以给出的数据为例。

        数据的存储为

        二叉树的形式为

          根据上图可以得出以下结论。

     （1）每层第一个元素的下标为2^(n-1)，最后一个元素的下标是2^n-1。

     （2）若元素的节点下标为i，则其所在的层数为log2i。(2为下标)

     【参考程序如下】

#include <iostream>
#include <math.h>
using namespace std;
const int N = 10010;
long long a[N],maxsize = -0x3f3f3f3;      //初始为负无穷大 

int main(int argc, char** argv) {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	cin >> a[i];       // a数组存储的是每个节点的权值
	int res;
	for(int i = 1; i <= n; i *= 2)
	{
		long long s = 0;
		for(int j = i; j <= i * 2 - 1 && j <= n;j++)
		{
			s += a[j];
		}
		if(s > maxsize)
		{
			maxsize = s;
			res = (int) log2(i) + 1;
		}
	 } 
	 cout << res;
	return 0;
}

【运行结果如下】