class Solution {
public:
int countHighestScoreNodes(vector<int>& parents) {
}
};
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
表示一棵二叉树。原站题解
javascript 解法, 执行用时: 512 ms, 内存消耗: 87 MB, 提交时间: 2023-05-05 17:19:27
/** * @param {number[]} parents * @return {number} */ 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; };
golang 解法, 执行用时: 136 ms, 内存消耗: 26.1 MB, 提交时间: 2023-05-05 17:19:11
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 := 0 var dfs func(int) int dfs = func(node int) int { score, size := 1, n-1 for _, ch := range children[node] { sz := dfs(ch) score *= sz size -= sz } if node > 0 { score *= size } if score == maxScore { ans++ } else if score > maxScore { maxScore = score ans = 1 } return n - size } dfs(0) return }
java 解法, 执行用时: 60 ms, 内存消耗: 62.4 MB, 提交时间: 2023-05-05 17:18:55
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; } }
python3 解法, 执行用时: 476 ms, 内存消耗: 111.5 MB, 提交时间: 2023-05-05 17:18:35
# dfs 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, 0 def dfs(node: int) -> int: score = 1 size = n - 1 for ch in children[node]: sz = dfs(ch) score *= sz size -= sz if node != 0: score *= size nonlocal maxScore, cnt if score == maxScore: cnt += 1 elif score > maxScore: maxScore, cnt = score, 1 return n - size dfs(0) return cnt