【问题描述】

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

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

注：根的深度是 1。

【输入格式】

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

【输出格式】

输出一个整数代表答案。

【样例输入】

7
1 6 5 4 3 2 1

【样例输出】

【评测用例规模与约定】

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

思路1

本题重点考察的是二叉树的有关性质，和存储结构二叉树关系不大。

由上图分析可知，当层数为j时，每层元素在数组中的地址在区间 [ 2^(j-1) , 2^j ) 中，这是核心点

然后将每层元素进行求和比较，即可得到权值之和最大所在的层数。因为是从第1层开始由下而上计算，所以之后某一层出现了和当前层权值之和相同时，无需更新层数，此时当前层就是深度最小的。

代码1

代码中用到<cmath>中的相关函数，常用函数小结如下：

函数名称	函数说明
floor (x)	向下取整，即不大于x的最大整数
ceil(x)	向上取整，即不小于x的最小整数
pow(x,y)	幂函数，即计算x的y次幂
sqrt(x)	开平方函数，即求x的平方根
round(x)	四舍五入函数，即四舍五入x得到离它最近的整数
log(x)	对数函数，即求以e为底x的对数，常用换底公式进行对数计算

#include<iostream>
#include<cmath>
using namespace std;
const int N = 100005;
long long a[N]={0};
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];//下标从1开始与完全二叉树的序号一致，便于操作 
	} 
	long max=0,sum=0;
	int i,j,depth=0;
	for(i=1;i<=floor(log(n)/log(2))+1;i++){//floor()为向下取整函数 
		sum=0;
		for(j=pow(2,i-1);j<pow(2,i);j++){
			sum+=a[j];
			if(j==n)break;//说明已经操作到最后一个结点，先跳出内循环 
		}
		if(sum>max){
			max=sum;
			depth=i;
		}
		if(j==n)break;//接着跳出外循环，计算结束 
	}
	cout<<depth;
	return 0;
}

思路2

思路1中是利用深度来求得各层元素在数组中地址的范围，然后累加求和比较

思路2则是采用在数组中设置“移动”变量pos，移动的距离为每层的元素个数

要注意的是要判断是否为满二叉树，因为题目中的图具有一定的迷惑性，完全二叉树不一定是满二叉树，所以要对最后一层的元素个数与那一层至多有多少元素进行比较，相等则为满二叉树，小于则是非满二叉树。

代码2

#include<iostream>
#include<cmath>
using namespace std;
const int N = 100005;
long long a[N]={0};
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	} 
	int deep=1,pos=0;
	long long max=0;
	int depth=floor(log(n)/log(2))+1;//含有n个结点的完全二叉树的深度 
	for(int i=1;i<=depth;i++){
		long long sum=0;
		int node=pow(2,i-1);//第i层最多的结点数 
		//非满二叉树 
		int temp=n-pos;//必须要先保存n-pos的值，因为pos是不断移动变化的 
		if(temp<node){
			for(int j=0;j<temp;j++){
				sum+=a[pos++];
			}
		} 
		//满二叉树 
		else{
			for(int j=0;j<node;j++){
				sum+=a[pos++];
			}
		}
		if(sum>max){
			max=sum;
			deep=i;
		}
	}
	cout<<deep<<endl;
	return 0;
}