统计最高分的节点数目

难度: Medium

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

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

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

示例 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 ）。

示例 2：

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

Submission

运行时间: 308 ms

内存: 47.0 MB

# class Solution:
#     def countHighestScoreNodes(self, parents: List[int]) -> int:
#         # 使用图表示树结构，图的键是父节点，值是子节点的列表
#         graph = collections.defaultdict(list)
#         n = len(parents)  # 总节点数
#         scores = [1] * n  # 初始化每个节点的得分为1

#         # 构建图结构
#         for i, num in enumerate(parents):
#             if num != -1:  # 如果不是根节点
#                 graph[num].append(i)  # 将子节点添加到父节点的列表中
#         # print(graph):  {2: [1, 3], 0: [2, 4]

#         # 深度优先搜索计算每个节点的得分
#         def dfs(node):
#             res = 1 # 以节点node为根的子树的节点数目
#             for child in graph[node]:  # 遍历当前节点的所有子节点(left and right)
#                 val = dfs(child)  # 递归计算子树的节点数
#                 res += val  # 更新当前子树的节点数
#                 scores[node] *= val  # *x*y
    
#             # 如果当前节点不是根节点，则还需要乘以其parent树的节点数
#             if node: # 不是0
#                 scores[node] *= (n - res) # n - x -y -1

#             return res  

#         dfs(0)
#         # 计算得分最高的节点数量
#         max_score = max(scores)  # 最高得分
#         return scores.count(max_score)  # 返回最高得分的节点数量

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        self.maxScore = 0  # 记录最大分数，用于cnt++
        self.cnt = 0  # 返回值，即最高得分节点数目
        self.n = len(parents)  # 节点总数，用于得到size用于计算三种情况下节点的个数
        self.children = [[] for _ in range(self.n)]  # 构图，用于dfs

        # 构建每个节点的子节点列表
        for i in range(self.n):
            p = parents[i]
            if p != -1:
                self.children[p].append(i)

        # 从根节点开始dfs搜索
        self.dfs(0)

        # 返回有最高得分节点的数目
        return self.cnt

    def dfs(self, node: int) -> int:
        score = 1
        size = self.n - 1  # 当前节点被删除
        for c in self.children[node]:
            t = self.dfs(c)  # 得到以当前节点孩子节点为根节点的树的节点个数
            score *= t  # 乘左右孩子数量
            size -= t  # 保存剩余节点个数

        # 判断是否为最初根节点，否则导致size=0
        if node != 0:
            score *= size  # 乘被删节点父节点所在树节点的节点个数

        # 代表出现了与最高分相同的节点，返回答案计数+1
        if score == self.maxScore:
            self.cnt += 1
        elif score > self.maxScore:
            self.maxScore = score
            self.cnt = 1

        return self.n - size  # 返回以当前节点node为根节点组成的树的节点总数

Explain

该题解采用深度优先搜索(DFS)的方法来解决问题。首先，通过父节点数组构建一个树的子节点列表表示。对每个节点，使用DFS来计算以该节点为根的子树的大小，并计算删除该节点后其他部分的大小乘积作为该节点的得分。在DFS过程中，同时更新最高得分和得分最高的节点数。整体过程避免了重复计算，每个节点只被访问一次，确保了效率。

时间复杂度: O(n)

空间复杂度: O(n)

# class Solution:
#     def countHighestScoreNodes(self, parents: List[int]) -> int:
        self.maxScore = 0  # 最大分数
        self.cnt = 0  # 最高得分的节点数量
        self.n = len(parents)  # 节点总数
        self.children = [[] for _ in range(self.n)]  # 子节点列表

        # 构建每个节点的子节点列表
        for i in range(self.n):
            p = parents[i]
            if p != -1:
                self.children[p].append(i)

        # 从根节点开始深度优先搜索
        self.dfs(0)

        # 返回最高得分的节点数目
        return self.cnt

    def dfs(self, node: int) -> int:
        score = 1  # 初始化分数为1
        size = self.n - 1  # 当前节点被删除后的剩余节点数
        for c in self.children[node]:
            t = self.dfs(c)  # 计算子树大小
            score *= t  # 更新分数
            size -= t  # 更新剩余节点数

        # 如果不是根节点，计算其父节点子树的大小
        if node != 0:
            score *= size  # 更新分数

        # 更新最高得分和计数
        if score == self.maxScore:
            self.cnt += 1
        elif score > self.maxScore:
            self.maxScore = score
            self.cnt = 1

        return self.n - size  # 返回子树大小

Explore

在构建子节点列表的过程中，通过遍历`parents`数组来完成。对于数组中的每个元素（除了根节点，其父节点索引为-1），我会将当前节点索引（即遍历的索引）添加到父节点的子列表中。这里使用`self.children[p].append(i)`实现，其中`p`是当前节点的父节点索引，`i`是当前节点索引。由于是直接根据`parents`数组进行操作，每个节点都会被正确地分配到其父节点的子列表中。

DFS函数通过递归的方式访问每个节点。对于每个节点，它首先计算其所有子节点的大小，并在此过程中累计分数。由于每个节点在DFS中只调用一次`dfs(c)`（其中`c`是子节点），这保证了每个节点只被访问一次。关于避免重复计算，每个节点的子树大小在首次计算后通过返回值传递给父节点，而不需要重新计算，这样有效避免了重复工作。

初始化分数为1是因为分数的计算依赖于乘积操作，且乘法的单位元是1。在遍历子节点时，每个子树大小与当前分数相乘，这样可以得到分离该节点后其他部分的大小乘积，作为该节点的得分。这种方法确实可能导致分数溢出，尤其是在处理大数据集或树深度较大时。在实际应用中，可能需要使用更大范围的变量类型或在某些语言中处理大整数操作以防止溢出。

在根节点的分数计算中，不需要包括其父节点子树的大小，因为根节点没有父节点。因此，对于根节点，其得分仅取决于其所有子树的大小的乘积。这与其他节点不同，因为非根节点需要计算包括其父节点中其余部分的大小。根节点的特殊处理是因为它在树结构中具有唯一性，作为树的最顶层节点。