LeetCode 力扣官方题解 | 2049. 统计最高分的节点数目
2049. 统计最高分的节点数目
题目描述
难易度：中等
给你一棵根节点为 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 表示一棵二叉树。
解决方案
方法一：深度优先搜素
思路
在一棵树中，当把一个节点和与它相连的所有边删除，剩余部分最多为三棵非空子树，即原节点的左子树（如果有），右子树（如果有），以及把以这个节点为根结点的子树移除所形成的子（除根结点外均有）。而这个节点的分数为这些子树的节点个数的乘积。我们可以先用 parents 数组统计出每个节点的子节点，然后使用深度优先搜索来计算以每个节点为根结点的子树的大小，同时计算每个节点的大小，作为深度优先搜索的返回值，最后统计最大分数出现的次数。在实现上，统计最大分数出现的次数可以放到深度优先搜索中完成，从而节省一部分空间。
代码
Python3
class Solution:def countHighestScoreNodes(self, parents: List[int]) -> int:n = len(parents)children = [[] for _ in range(n)]for node, p in enumerate(parents):if p != -1:children[p].append(node)maxScore, cnt = 0, 0def dfs(node: int) -> int:score = 1size = n - 1for ch in children[node]:sz = dfs(ch)score *= szsize -= szif node != 0:score *= sizenonlocal maxScore, cntif score == maxScore:cnt += 1elif score > maxScore:maxScore, cnt = score, 1return n - sizedfs(0)return cnt
Java
class Solution {long maxScore = 0;int cnt = 0;int n;List<Integer>[] children;public int countHighestScoreNodes(int[] parents) {n = parents.length;children = new List[n];for (int i = 0; i < n; i++) {children[i] = new ArrayList<Integer>();}for (int i = 0; i < n; i++) {int p = parents[i];if (p != -1) {children[p].add(i);}}dfs(0);return cnt;}public int dfs(int node) {long score = 1;int size = n - 1;for (int c : children[node]) {int t = dfs(c);score *= t;size -= t;}if (node != 0) {score *= size;}if (score == maxScore) {cnt++;} else if (score > maxScore) {maxScore = score;cnt = 1;}return n - size;}}
C#
public class Solution {long maxScore = 0;int cnt = 0;int n;IList<int>[] children;public int CountHighestScoreNodes(int[] parents) {n = parents.Length;children = new IList<int>[n];for (int i = 0; i < n; i++) {children[i] = new List<int>();}for (int i = 0; i < n; i++) {int p = parents[i];if (p != -1) {children[p].Add(i);}}DFS(0);return cnt;}public int DFS(int node) {long score = 1;int size = n - 1;foreach (int c in children[node]) {int t = DFS(c);score *= t;size -= t;}if (node != 0) {score *= size;}if (score == maxScore) {cnt++;} else if (score > maxScore) {maxScore = score;cnt = 1;}return n - size;}}
C++
class Solution {public:long maxScore = 0;int cnt = 0;int n;vector<vector<int>> children;int dfs(int node) {long score = 1;int size = n - 1;for (int c : children[node]) {int t = dfs(c);score *= t;size -= t;}if (node != 0) {score *= size;}if (score == maxScore) {cnt++;} else if (score > maxScore) {maxScore = score;cnt = 1;}return n - size;}int countHighestScoreNodes(vector<int>& parents) {this->n = parents.size();this->children = vector<vector<int>>(n);for (int i = 0; i < n; i++) {int p = parents[i];if (p != -1) {children[p].emplace_back(i);}}dfs(0);return cnt;}};
C
int dfs(int node, long * maxScore, int * cnt, int n, const struct ListNode ** children) {long score = 1;int size = n - 1;for (struct ListNode * curr = children[node]; curr; curr = curr->next) {int t = dfs(curr->val, maxScore, cnt, n, children);score *= t;size -= t;}if (node != 0) {score *= size;}if (score == *maxScore) {(*cnt)++;} else if (score > *maxScore) {*maxScore = score;*cnt = 1;}return n - size;}int countHighestScoreNodes(int* parents, int parentsSize){int n = parentsSize;int cnt = 0;long maxScore = 0;struct ListNode ** children = (struct ListNode **)malloc(sizeof(struct ListNode *) * n);for (int i = 0; i < n; i++) {children[i] = NULL;}for (int i = 0; i < n; i++) {int p = parents[i];if (p != -1) {struct ListNode * node = (struct ListNode *)malloc(sizeof(struct ListNode));node->val = i;node->next = children[p];children[p] = node;}}dfs(0, &maxScore, &cnt, n, children);for (int i = 0; i < n; i++) {for (struct ListNode * curr = children[i]; curr; ) {struct ListNode * next = curr->next;free(curr);curr = next;}}free(children);return cnt;}
Golang
func countHighestScoreNodes(parents []int) (ans int) {n := len(parents)children := make([][]int, n)for node := 1; node < n; node++ {p := parents[node]children[p] = append(children[p], node)}maxScore := 0var dfs func(int) intdfs = func(node int) int {score, size := 1, n-1for _, ch := range children[node] {sz := dfs(ch)score *= szsize -= sz}if node > 0 {score *= size}if score == maxScore {ans++} else if score > maxScore {maxScore = scoreans = 1}return n - size}dfs(0)return}
JavaScript
var countHighestScoreNodes = function(parents) {const n = parents.length;const children = new Array(n).fill(0);let maxScore = 0;let cnt = 0;for (let i = 0; i < n; i++) {children[i] = [];}for (let i = 0; i < n; i++) {const p = parents[i];if (p !== -1) {children[p].push(i);}}const dfs = (node) => {let score = 1;let size = n - 1;for (const c of children[node]) {let t = dfs(c);score *= t;size -= t;}if (node !== 0) {score *= size;}if (score === maxScore) {cnt++;} else if (score > maxScore) {maxScore = score;cnt = 1;}return n - size;}dfs(0);return cnt;};
复杂度分析
时间复杂度：O(n)，其中 nn 是树的节点数。预处理，深度优先搜索均消耗 O(n) 时间。
空间复杂度：O(n)。统计每个节点的子节点消耗 O(n) 空间，深度优先搜索的深度最多为 O(n) 空间。
BY /
本文作者：力扣
声明：本文归“力扣”版权所有，如需转载请联系。
微信扫码关注该文公众号作者
戳这里提交新闻线索和高质量文章给我们。
来源: qq
点击查看作者最近其他文章