试题 历届真题 完全二叉树的权值【第十届】【省赛】【A组】
问题描述
给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从
上到下、从左到右的顺序依次是 A1, A2, · · · AN,如下图所示:
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点
权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。
注:根的深度是 1。输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,
A2, · · · AN 。输出格式
输出一个整数代表答案。
样例输入
7
1 6 5 4 3 2 1样例输出
2
思路:用一个数组来存这棵树,1为根节点所在,然后左孩子就是i*2,右孩子就是i * 2+1 ;树存完后,层序遍历一遍就ok了,
这里的层序遍历的时候,我们有两层循环,外层是q队列不为空,内层是将当前层的结点全部pop(),这样就可以计算整层的权值和了
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5+5;
//每个点有下标,和值,我这里用一个结构体表示,
typedef struct{
int no, value;
}Node;
//队列
queue<Node> q;
//tree存树的数组,total[i]表示第i层的权值和,为什么是18?
//因为2^18已经大于了本题的最大范围了
int tree[N], n, total[18];
int main()
{
//表示计算第no层的权值
int no = 1;
cin >> n;
for ( int i = 1; i <= n; ++i ) {
cin >> tree[i];
}
//把头结点入队
Node t = {1, tree[1]};
q.push(t);
//层序遍历
while ( !q.empty() ) {
//size表示当前队列中的元素个数,即当前层的结点有多少个
int size = q.size(), sum = 0;
while ( size-- ) {
Node temp = q.front();
q.pop();
//累加当前层权值
sum += temp.value;
//有左孩子
if ( temp.no * 2 <= n ) {
Node te = {temp.no*2, tree[temp.no*2]};
q.push(te);
}
//有右孩子
if ( temp.no * 2 + 1 <= n ) {
Node te = {temp.no*2+1, tree[temp.no*2+1]};
q.push(te);
}
}
total[no++] = sum;
}
int maxn = total[1], maxno = 1;
for ( int i = 1; i < no; ++i ) {
if ( maxn < total[i] ) {
maxn = total[i];
maxno = i;
}
}
cout << maxno << endl;
return 0;
}
看图吧:
end