牛客编程巅峰赛S2第1场 - 青铜&白银&黄金 第二题 Tree4 解题思路

第二题思路
首先确定以下几点：
1、每一个结点的价值等于结点编号乘以结点深度
2、整个二叉树的价值等于所有结点的价值之和
3、二叉树每一层所有结点的深度相同，也就是结点层数

二叉树有以下特点：
1、每层所有结点编号构成一个等差数列，其项数就是当前层的结点总个数，同时也是当前层的首项
2、所有层的第一个编号，也就是每层的首项构成一个等比数列

设当前结点的深度，也即所在层数为k，
每层结点编号连续，构成一个递增的等差数列，其公差为1，首项为2^(k-1),同时也是前一层首项的2倍,最多有2^(k-1)项，
因此，可根据等差数列求和公式直接求得当前层所有结点的价值和
设第k层共有β个结点，则第k层的价值和为：

若第k层结点全部包括，则：

若第k层结点未全部包括，即最后一层，则：

然后对所有项求和即可，每求一次，层数（深度）k加1，相应的首项乘2，乘2可用左移1位解决，整除2可用右移解决
Python代码如下,代码中的v表示总价值，k为结点层数，a为首项，b为项数：

class Solution:
    def tree4(self , n ):
        v,k,a = 1,2,2
        while a <= n: 
            b = a if (a<<1)<=n else n-a+1
            v,k,a = v+((a*b+(b*(b-1)>>1))*k),k+1,a<<1
        return v % 998244353

后续：
这种算法代码还算量还算少，但是也是比较耗时的，因为其实只有最后一层的项数才需要重新计算，前面所有层，层数确定，项数就是首项值，可以直接计算，第k层全部结点价值和公式如下：