本文涉及知识点

C++DFS
打开打包代码的方法兼述单元测试

LeetCode2049. 统计最高分的节点数目

给你一棵根节点为 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 <= 10⁵
parents[0] == -1
对于 i != 0 ，有 0 <= parents[i] <= n - 1
parents 表示一棵二叉树。

DFS

vChild[cur] 记录cur的左右孩子。
cnt[cur] 记录以cur为根的子树数量。
后序DFS获取各子树数量。
枚举各节点获取各节点cur分数：
ans =1
remain = n -1
枚举各孩子child
{
ans *= cnt[child]
remain -= cnt[child]
}
ans *= max(remain,1)
有序映射记录各分数数量。

代码

核心

class Solution {
		public:
			int countHighestScoreNodes(vector<int>& parents) {
				const int N = parents.size();
				vector<vector<int>> vChild(N);
				for (int i = 0; i < N; i++) {
					if (-1 == parents[i]) { continue; }
					vChild[parents[i]].emplace_back(i);
				}
				vector<int> nodeCount(N,1);
				function<void(int)> DFS = [&](int cur) {
					for (const auto& child : vChild[cur]) {
						DFS(child);
						nodeCount[cur] += nodeCount[child];
					}
				};
				DFS(0);
				map<long long, int> mCount;
				for (int i = 0; i < N; i++) {
					long long ans = 1;
					for (const auto& child : vChild[i]) {
						ans *= nodeCount[child];
					}
					ans *= max(1, N - nodeCount[i]);
					mCount[ans]++;
				}
				return mCount.rbegin()->second;
			}
		};

单元测试

vector<int> parents;

	public:

		TEST_METHOD(TestMethod11)
		{
			parents = { -1,2,0,2,0 };
			auto res = Solution().countHighestScoreNodes(parents);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			parents = { -1,2,0 };
			auto res = Solution().countHighestScoreNodes(parents);
			AssertEx(2, res);
		}