[数据结构与算法]完全二叉树的权值（2019年蓝桥杯真题）

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

?

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

注:根的深度是 1。

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

输出
输出一个整数代表答案。

输入样例
7
1 6 5 4 3 2 1

计算机内部是这样呈现的：

? ? ? ? ? ? ? 1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 深度为1

? ?6? ? ? ? ? ? ? ? ?? 5? ? ? ? ? ? ? ? ? ? sum=11? ? ? ? ? ? ?深度为2

4? ? ?3? ? ? ? ? ?2? ? ? ?1? ? ? ? ? ? ? ?sum=10? ? ? ? ? ? ?深度为3

故输出样例为2

数据范围
对于所有评测用例，1 ≤ N≤ 100000，?100000 ≤ Ai≤ 100000

思路
就是用for循环控制同一深度的子叶输入，下一层都是上一层的二倍，然后累加进行比较。话不多说，上代码：

#include<iostream>

using namespace std;

int shu(int n)
{
	int i, j, num;
	int ans = 0, treedepth = 0, sum = 0, leaf = 1, figure = 0;

	for (i = 1; i <= n; i++) 
	{
		if (i == 1) 
			leaf = 1;
		else 
			leaf *= 2;
		sum = 0;
		for (j = 1; j <= leaf; j++)
		{
			if (figure >= n) break;
			cin >> num;
			sum += num;
			figure++;
		}
		if (ans < sum)
		{
			ans = sum;
			treedepth = i;
		}
	}
	return treedepth;
}

int main() {
	int n,deep;

	cin >> n;
	deep = shu(n);
	cout << deep << endl;

	return 0;
}

祝各位小伙伴4月9号的蓝桥杯省赛顺利！
?