食品网站建设书,网站建设网络推广书生,经开区网站建设,一流的江苏网站建设文章目录1. 题目2. 解题1. 题目
给你一棵根节点为 0 的 二叉树 #xff0c;它总共有 n 个节点#xff0c;节点编号为 0 到 n - 1 。 同时给你一个下标从 0 开始的整数数组 parents 表示这棵树#xff0c;其中 parents[i] 是节点 i 的父节点。 由于节点 0 是根#xff0c;所…
文章目录1. 题目2. 解题1. 题目
给你一棵根节点为 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 分别是节点 13 和 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 10^5
parents[0] -1
对于 i ! 0 有 0 parents[i] n - 1
parents 表示一棵二叉树。来源力扣LeetCode 链接https://leetcode-cn.com/problems/count-nodes-with-the-highest-score 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
建图dfs自底向上求子树节点数量dfs求取每个节点的得分
class Solution {vectorvectorint g;vectorlong long score;long long ans 0, n;
public:int countHighestScoreNodes(vectorint parents) {n parents.size();g.resize(n);score.resize(n);for(int i 1; i n; i)g[parents[i]].push_back(i);vectorint node(n, 0);dfs(0, node);dfs1(0, node);int ct 0;for(auto s : score){if(s ans)ct;}return ct;}int dfs(int x, vectorint node){node[x];for(auto y : g[x])node[x] dfs(y, node);return node[x];}void dfs1(int x, vectorint node){for(auto y : g[x])dfs1(y, node);if(g[x].size()0) score[x] n-1;else if(g[x].size()1){int n1 node[g[x][0]];score[x] 1LL*n1*((n-1-n1)0? 1 :(n-1-n1));}else{int n1 node[g[x][0]];int n2 node[g[x][1]];score[x] 1LL*n1*n2*((n-1-n1-n2)0? 1 : (n-1-n1-n2));}ans max(ans, score[x]);}
};276 ms 132.7 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
