文章目录
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 （分别是节点 1，3 和 4 ）。
输入：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 表示一棵二叉树。
2. 解题
- 建图，dfs，自底向上求子树节点数量
- dfs，求取每个节点的得分
class Solution { vector<vector<int>> g; vector<long long> score; long long ans = 0, n; public: int countHighestScoreNodes(vector<int>& parents) { n = parents.size(); g.resize(n); score.resize(n); for(int i = 1; i < n; ++i) g[parents[i]].push_back(i); vector<int> 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, vector<int>& node) { node[x]++; for(auto y : g[x]) node[x] += dfs(y, node); return node[x]; } void dfs1(int x, vector<int>& 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++
