完全二叉树的权值-蓝桥183-二叉树

本文主要是介绍完全二叉树的权值-蓝桥183-二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注意用long long

法1：按数的序号加

pow在c的math头文件里，所以在c++的cmath

非常注意内部按数的序号加每层权值和时，一定要添加i<=n啊，因为这是完全二叉树，不是满二叉树，最后一层可能缺胳膊少腿的

完整代码：

#include<iostream>
#include<cmath>
using namespace std;typedef long long ll;
ll a[100010];int main(){int mindeep=1,n;cin>>n>>a[1];for(int i=2;i<=n;i++){cin>>a[i];}ll max=a[1];int i=2,deep=2;while(i<=n){ll sum=0;for(;i<=n&&i<=pow(2,deep)-1;i++)//因为我少些了i<=n而错啊啊啊啊啊{sum+=a[i];}if(sum>max){max=sum;mindeep=deep;}deep++;}cout<<mindeep;return 0;
}

法2：按层加

引入sum[]数组来记录第几层的权值和

求序号在二叉树的第几层，就是用它除以2，能除几次在第几层，其实就是log2(x)，但是直接用log函数可能有问题

x>>=1即左移两位，等价于x=x>>1;  或者x=x/2;

这里有三种求最大权值和的最浅层数，13同理，只有23是对的

1	while(deep--){//从最底层往上走，求得的一定是深度最小的if(max<=sum[deep]){max=sum[deep];mindeep=deep;}}
2	for(int i=2;i<=deep;i++){if(max<sum[i]){max=sum[i];mindeep=i;}}
3	for(int i=deep;i>=1;i--){//从最底层往上走，求得的一定是深度最小的//记得要包含i=1if(max<=sum[i]){max=sum[i];mindeep=i;}}

完整代码：

​
#include<iostream>
#include<cmath>
using namespace std;typedef long long ll;
ll a[100010];ll sum[100];//sum[i]为第i层的权值和
int deeplog(ll x){//能求出序号x在二叉树的第几层int deep=0;while(x){x>>=1;deep++;}return deep;
}
int main(){int n;cin>>n;ll deep=deeplog(n);//规定层数1~for(int i=1;i<=n;i++){cin>>a[i];sum[deeplog(i)]+=a[i];}ll max=sum[1];int mindeep=1;
/*	while(deep--){//从最底层往上走，求得的一定是深度最小的if(max<=sum[deep]){max=sum[deep];mindeep=deep;}}*/
/*	for(int i=2;i<=deep;i++){if(max<sum[i]){max=sum[i];mindeep=i;}}*/for(int i=deep;i>=1;i--){//从最底层往上走，求得的一定是深度最小的//记得要包含i=1if(max<=sum[i]){max=sum[i];mindeep=i;}}cout<<mindeep;return 0;
}​

这篇关于完全二叉树的权值-蓝桥183-二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---