【问题描述】
给定一棵包含 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。
思路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;
}总结
思路2的做法，在进行非满二叉树相关操作时，我一开始的代码有个细节错误，就是没有保存n-pos的值然后直接进行下面操作了，因为pos是不断移动变化的，所以n-pos也是变化的，而我们所要的是一开始操作时的n-pos值进行非满二叉树的判定。这也是10个测试点硬是有一个一直不通过的原因！
错误代码：
正确代码：
可能发现后现在觉得这就是一个考虑不周全的小问题，但是自己找了半天，结果让朋友帮我看，五分钟就找到原因了，真所谓“ 当局者迷，旁观者清 ”，所以以后在一些小细节的处理上一定一定要更加严谨！要快，但更要准。