来源：力扣（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; } };
运行结果
