LeetCode-2049 统计最高分的结点数
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-nodes-with-the-highest-score
题目描述
给你一棵根节点为 0 的 二叉树 ,它总共有 n 个节点,节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵树,其中 parents[i] 是节点 i 的父节点。由于节点 0 是根,所以 parents[0] == -1 。
一个子树的 大小 为这个子树内节点的数目。每个节点都有一个与之关联的 分数 。求出某个节点分数的方法是,将这个节点和与它相连的边全部 删除 ,剩余部分是若干个 非空 子树,这个节点的 分数 为所有这些子树 大小的乘积 。
请你返回有 最高得分 节点的 数目 。
示例 1:
输入:parents = [-1,2,0,2,0]
输出:3
解释:
- 节点 0 的分数为:3 * 1 = 3
- 节点 1 的分数为:4 = 4
- 节点 2 的分数为:1 * 1 * 2 = 2
- 节点 3 的分数为:4 = 4
- 节点 4 的分数为:4 = 4
最高得分为 4 ,有三个节点得分为 4 (分别是节点 1,3 和 4 )。
示例 2:
输入:parents = [-1,2,0]
输出:2
解释:
- 节点 0 的分数为:2 = 2
- 节点 1 的分数为:2 = 2
- 节点 2 的分数为:1 * 1 = 1
最高分数为 2 ,有两个节点分数为 2 (分别为节点 0 和 1 )。
提示:
n == parents.length
2 <= n <= 105
parents[0] == -1
对于 i != 0 ,有 0 <= parents[i] <= n - 1
parents 表示一棵二叉树。
解题思路
首先parant数组存储形式对于数来说不直观,很难进行操作,所以遍历parant数组,利用邻接链表建立一颗二叉树。然后使用二叉树的后续遍历,分别将左右子树和分数全求出来,进行比较和计数,需要注意int相乘可能会越界,需要使用long。
代码展示
class Solution {
public:
vector<vector<int>> mvviTree;
long long miMax;
int miCount;
void dfs(int root, int &count)
{
int iCount = 0;
long long iCount1 = 1;
count = 1;
for(auto iter:mvviTree[root])
{
dfs(iter, iCount);
count += iCount;
iCount1 *= iCount;
}
if(root)
iCount1 *= (mvviTree.size() - count);
if(iCount1 > miMax)
{
miMax = iCount1;
miCount = 1;
}
else if(iCount1 == miMax)
{
miCount++;
}
}
int countHighestScoreNodes(vector<int>& parents) {
int n = parents.size();
miCount = 0;
miMax = 0;
mvviTree.resize(n, vector<int>());
int iCount = 0;
for(int i = 1; i < n; i++)
{
mvviTree[parents[i]].push_back(i);
}
dfs(0, iCount);
return miCount; }
};
运行结果
最新文章
- 【poj3615】 Cow Hurdles
- 检查C++内存泄露
- GO语言练习:第一个Go语言工程--排序
- 利用zabbix监控某个目录大小
- Linux rename命令
- SQL Server 高性能写入的一些总结
- js 超级玛丽(未完成)
- HDOJ(HDU) 1555 How many days?(水题)
- OFBIZ分享:利用Nginx +Memcached架设高性能的服务
- ELK日志系统:Elasticsearch + Logstash + Kibana 搭建教程(转)
- 深入浅出requireJS-1
- ccw-ide
- JS的作用域浅谈
- c# 事件路由器
- ROS学习笔记
- 100个iOS开发面试题汇总
- rename_windows.go
- asp.net上传图片到服务器
- B - Tree Rotations HYSBZ - 2212 (线段树合并)
- CI框架2.x的验证码中所遇问题解决
热门文章
- Jmeter ForEach 循环控制器
- git相关问题解析,你想要的都有&#128293;
- NOIP-2022游寄
- vlc qt player 播放器开发实例
- 本机无法配置远程服务器上的MySQL ODBC连接驱动
- Java long类型转换易犯的错误
- VUE assets里的scss没有引用会被打包进代码里,本地代码和打包后的代码样式不一致解决办法
- Grafana 系列文章(一):基于 Grafana 的全栈可观察性 Demo
- VMware vSphere vCenter ServerAppliance 7.0安装配置
- 1.31 wlx 魔怔 9 解法交互题小结