题目描述
给定一棵包含 N个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是 A1,
A2,⋅⋅⋅AN
如下所示:
A1
A2 A3
A4 A5 A6 A7
…
( 一个完全二叉树)
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点权值之和最大?
如果有多个深度的权值和同为最大,请你输出其中最小的深度。
输入格式
第一行包含一个整数
N
第二行包含 N个整数 A1,A2,⋅⋅⋅AN。
数据范围
1≤N≤10^5
1 <= Ai <= 10^5
样例
输入样例:
7
1 6 5 4 3 2 1
输出样例:
2
算法1
(暴力)
暴力大法好
不才对于所有题目的思路,我坚信就没有暴力做不了的题儿
时间复杂度
[弱鸡没有算这个复杂度]
思路
既然题意说需要一个完全二叉树,那么我们就建立一个完全二叉树;
节点
struct Node
{
long long data;
struct Node * pLeft;
struct Node * pRight;
};
struct Node tr[N];
-
既然是完全二叉树,那么我们就可以知道每一个节点
当2i + 1 <= n 时 证明i 节点有左孩子
当2i + 2 <= n 时 证明i 节点有右孩子,通过这个思路直接建立一个完全二叉树
此时完全二叉树的层数 k = log2(n) + 1
这个时候进行一个搜索每一层进行加和就可以了 -
加和的时候我使用了两个队列,当层数为奇数层时候,在q1队列进行计算结果并把孩子节点放进q2队列
当层数为偶数的时候,在q2队列进行计算结果并把孩子节点放进q1队列
同时求和就可以了。 -
然后循环存储数值的数组st[N],找到最大值和下标。
-
我有个疑问就是, 我通过dfs()函数里面的返回值进行遍历数组就会出错,使用log2(n)+1就直接AC,如果大佬看到了还请帮助我解决这个疑问再次先行谢过
C++ 代码
//完全二叉树
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
using namespace std;
const int N = 100020;
typedef struct Node
{
long long data;
struct Node* pLeft;
struct Node* pRight;
}Mytree;
Mytree tr[N];
int n;
long long st[N];
void CreateTree(Mytree* p,int len) //建立二叉树
{
for (int i = 0; i < len / 2; i++)
{
if (2 * i + 1 <= n)
{
p[i].pLeft = &p[2 * i + 1];
}
if (2 * i + 2 <= n)
{
p[i].pRight = &p[2 * i + 2];
}
}
}
void dfs(Mytree *pRoot) //计算结果
{
if (pRoot == NULL) return ;
int i = 1;
queue<Mytree*> q;
queue<Mytree*> q2;
q.push(pRoot);
while (!q.empty() || !q2.empty())
{
Mytree * now = NULL;
if (i % 2 == 0 && !q2.empty())//偶数层进入第二个队列并把孩子放进第一个队列
{
now = q2.front();
st[i] += now->data;
if(now->pLeft != NULL)
q.push(now->pLeft);
if(now->pRight != NULL)
q.push(now->pRight);
q2.pop();
if (q2.empty())
i++;
}
else if(i % 2 == 1 && !q.empty()) //奇数层第一个队列并把孩子放进第一个队列
{
now = q.front();
st[i] += now->data;
if(now->pLeft != NULL)
q2.push(now->pLeft);
if (now->pRight!= NULL)
q2.push(now->pRight);
q.pop();
if (q.empty())
i++;
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%lld", &tr[i].data);
tr[i].pLeft = NULL;
tr[i].pRight = NULL;
}
CreateTree(tr, n);
dfs(tr);
// for (long long i = 1; i <= log2(n)+1; i++)
// {
// cout<<st[i]<< " ";
// }
// cout<<endl;
long long maxv = LONG_MIN;
long long ans = 1;
for (long long i = 1; i <= log2(n)+1; i++)
{
if (st[i] > maxv)
{
maxv = st[i];
ans = i;
}
}
printf("%lld\n", ans);
return 0;
}