完全二叉树的权值问题

前言

许多小伙伴刚刚接触二叉树的时候对二叉树的存储不太敏感，对于如何利用二叉树的性质解题存在盲区，这篇博客将会带领大家了解二叉树的存储性质在解题当中的作用。同时将会给出两种不同风格的代码【当然核心的原理上都是一样的】供大家参考，喜欢的小伙伴可以点个赞啦！
其他二叉树有关的题目如下：
动态求连续区间和+数列区间最大值（快速掌握线段树的基本性质及应用）

题目描述

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

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

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

注：根的深度是 1。

输入格式
第一行包含一个整数 N。

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

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

数据范围
1≤N≤105,
−105≤Ai≤105
输入样例：

7
1 6 5 4 3 2 1

输出样例：

2

知识预备【二叉树的存储】

定义【官方】

二叉树是一种常见的树状数据结构，它由一组称为节点的元素组成，这些节点通过指向其他节点的引用（通常称为左子节点和右子节点）来建立层次关系。

二叉树的特点包括：

• 每个节点最多有两个子节点，分别称为左子节点和右子节点。
• 左子节点的值小于或等于父节点的值，右子节点的值大于父节点的值。
• 每个节点最多有一个父节点，除了根节点没有父节点。
• 二叉树可以是空树，即没有任何节点。

以下是一个二叉树的示例图形表示：

      A
     / \
    B   C
   / \      \
  D   E   F

在这个示例中，节点A是根节点，节点B和C是A的子节点，节点D和E是B的子节点，节点F是C的子节点。

二叉树可以用不同的方式来实现，包括链式存储和数组存储。链式存储是指使用节点对象和引用来表示二叉树，而数组存储是指使用数组来表示二叉树。

自定义

上面的解释比较抽象，这里会给出图片帮助大家理解：以题目中的输入数据为例

二叉树的存储
可能有小伙伴看到二叉树是二维图形，所以需要一个二维数组去储存。其实不是这样，看图

总结出来的规律如下，看图

题目分析

将二叉树看成两个部分，叶子结点所在的那一层【叶子节点当中包含空节点】，除了叶子节点外的层数
每一层开始的数组下标都是 1 << (u-1) ，结束的下标都是 (1<<u)-1[叶子结点那层除外]
由此我们用递归去解决：用cnt数组记录每一层权值总和

void dfs(int u){
    if(n<=((1<<u)-1)) return;//这里是为了排除
    for(int i=1<<(u-1);i<(1<<u);i++){
        cnt[u]+=a[i];
    }
    dfs(u+1);
}

接着找到最后一层，计算最后一层的权值总和

for(int j=1;j<=n;j++){
        if((1<<j)-1>=n){
            flag=j;
            break;
        }
    }
    for(int i=(1<<(flag-1));i<=n;i++){
        cnt[flag]+=a[i];
    }

最后比较得出结论：

	ans=1;
    res=cnt[1];
    for(int i=2;i<=200;i++){
       if(!cnt[i]) break;
        if(cnt[i]>res){
            res=cnt[i];
            ans=i;
        }
    }

按部就班的代码

#include<iostream>
using namespace std;
const int N = 1e5 + 7;
long long  n,res,ans;
long long a[N],cnt[N];
void dfs(int u){// u 代表层数
    if(n<=((1<<u)-1)) return;
    for(int i=1<<(u-1);i<(1<<u);i++){
        cnt[u]+=a[i];
    }
    dfs(u+1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(1);
    
    int flag=0;
    for(int j=1;j<=n;j++){
        if((1<<j)-1>=n){
            flag=j;
            break;
        }
    }
    for(int i=(1<<(flag-1));i<=n;i++){
        cnt[flag]+=a[i];
    }
    ans=1;
    res=cnt[1];
    for(int i=2;i<=200;i++){
       if(!cnt[i]) break;
        if(cnt[i]>res){
            res=cnt[i];
            ans=i;
        }
    }
    
    cout<<ans<<endl;
}

精简优化的代码

#include <iostream>

using namespace std;
const int N = 1e5 + 7;

long long a[N];

int main() {
    int n;
    cin >> n;
    
    for(int i=1;i<=n;i++) cin>>a[i];
    long long res=  -1e18;//记录最大值
    int depth=1;//记录层数
    int ans=1;//记录最终结果值
    long long sum;//记录每一层的和
    for(int i=1;i<=n;i*=2){//代表层数
        sum=0;//每次进入到下一层都要记得重置sum
        for(int j=i;j<=n && j<=i*2-1;j++){
            sum+=a[j];
        }
        if(sum>res){
            res=sum;
            ans=depth;
        }
        depth++;
    }
    cout<<ans<<endl;
}

总结

以上就是有关二叉树存储的介绍，其他更多高难度题目可以在前言中查看，喜欢的小伙伴可以点个关注啦！