2049_统计最高分的节点数目

难度：中等

题目

给你一棵根节点为 0 的 二叉树 ，它总共有 n 个节点，节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵树，其中 parents[i] 是节点 i 的父节点。由于节点 0 是根，所以 parents[0] == -1 。

一个子树的 大小 为这个子树内节点的数目。每个节点都有一个与之关联的 分数 。求出某个节点分数的方法是，将这个节点和与它相连的边全部 删除 ，剩余部分是若干个 非空 子树，这个节点的 分数 为所有这些子树 大小的乘积 。

请你返回有 最高得分 节点的 数目 。

示例

示例一：

example-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 ）。

示例二：

example-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 表示一棵二叉树。

解题

可以先用 $parents$ 数组统计出每个节点的子节点，然后使用深度优先搜索来计算以每个节点为根结点的子树的大小，同时计算每个节点的大小，作为深度优先搜索的返回值，最后统计最大分数出现的次数。

统计每个节点的子节点：

1
2
3
4
5
6
7
8
9
10
11
12
List<Integer>[] children;

children = new List[n];
for (int i = 0; i < n; i++) {
  children[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
  int p = parents[i];
  if (p != -1) {
    children[p].add(i);
  }
}

使用深度优先搜索子树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int dfs(int node) {
  long score = 1;
  int sum = 1;
  // 遍历node的子节点
  for (int num : children[node]) {
    int t = dfs(num);
    // 分数 = 子树节点数乘积
    score *= t;
    // 统计已计算节点数
    sum += t;
  }
  if (node != 0) {
    // 非根节点需要乘以非子树节点个数
    // 即 根节点 = 左子树*右子树
    // 非根节点= 左子树 * 右子树 * 非此树
    score *= n - sum;
  }
  // 统计最高分数
  if (maxScore == score) {
    count++;
  } else if (score > maxScore) {
    maxScore = score;
    count = 1;
  }
  // 返回当前子树的节点数
  return sum;
}