【蓝桥杯】完全二叉树的权值

二叉树的权值"/>

【蓝桥杯】完全二叉树的权值

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

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？

如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

输入格式

第一行包含一个整数 N。

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

输出格式

输出一个整数代表答案。

数据范围

1≤N≤,
−≤Ai≤

输入样例：

7
1 6 5 4 3 2 1

输出样例：

2

完全二叉树的概念：

        一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

思路：

        双指针，记录起始位置和当前层二叉树的中元素的个数，利用一层循环求出总和并比较即可，可以当成满二叉树处理（下一层的节点数是上一层的两倍），当所求的元素总数与题目给出的 n 相同时，跳出循环。

完整代码（C++）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N = 1e5 + 10;int a[N];
//res.first 记录总和， res.second 记录层数
pair<long long, int> res = {0, 0}; int main()
{int n;cin >> n;for(int i = 1; i <= n; i++)scanf("%d", &a[i]);res = {a[1], 1};// i， j为指针头和尾 depth为深度 step为步长（即每层元素的个数）int i, j, depth = 1, step = 1; for(i = 1; i <= n; i = j, depth++){long long tmp = 0;for(j = i; j <= i + step - 1 && j <= n; j++){tmp += a[j];}//如果两层的和相同，输出最小层，因此所求的和要严格大于之前所求最大值if(tmp > res.first) {res.first = tmp;res.second = depth;}step *= 2;}cout << res.second << endl;return 0;
}