二叉树的权值"/>
【蓝桥杯】完全二叉树的权值
给定一棵包含 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;
}
更多推荐
【蓝桥杯】完全二叉树的权值
发布评论