首页 > 试题广场 >

Tree IV

[编程题]Tree IV
  • 热度指数：307 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一棵有n个结点的标准的完全二叉树（即，若父结点编号为x，则它的两个子结点的编号分别为和），定义每个结点的价值为xdep_x，即每个点的编号乘以每个点的深度（深度即为从根结点到这一结点最短路径经过的点的个数，定义根结点1的深度为1）。

请你求解这棵树中每个结点的价值和（由于答案可能会很大，请你对998244353取模），即。

完全二叉树：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第 k 层所有的结点都连续集中在最左边。
例如（图为一棵标准的完全二叉树）：

示例1

输入

2

输出

5
示例2

输入

5

输出

38

说明

其计算公式为：1 * 1 + (2 + 3) * 2 + (4 + 5) * 3 = 38 （此式乘号前面为结点编号的和，后面为这些节点对应的深度）

备注:
数据满足：


算法知识视频讲解
开通博客
头像 旭日东升BJFU
发表于 2020-11-17 21:10:44
A:Tree IV 刚开始看错题目，以为n<=100000.。。 直接写个二叉树遍历。。T了，然后快速改了下，分层等差数列统计即可。。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 乐观的lishan
发表于 2020-11-18 14:51:40
第二题思路首先确定以下几点：1、每一个结点的价值等于结点编号乘以结点深度2、整个二叉树的价值等于所有结点的价值之和3、二叉树每一层所有结点的深度相同，也就是结点层数 二叉树有以下特点：1、每层所有结点编号构成一个等差数列，其项数就是当前层的结点总个数，同时也是当前层的首项2、所有层的第一个编号，也就 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Free的午后
发表于 2020-11-18 12:17:10
链接：https://ac.nowcoder.com/acm/contest/9004/B直接上代码 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

树
难度：
2条回答 1990浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号