鲅鱼圈网站建设,安全证查询官网,厦门做网站多少,视频做网站2049. 统计最高分的节点数目题目算法设计#xff1a;深度优先搜索题目
传送门#xff1a;https://leetcode.cn/problems/count-nodes-with-the-highest-score/ 算法设计#xff1a;深度优先搜索
这题的核心是计算分数。
一个节点的分数 左子树节点数 右子树节点数 除自… 2049. 统计最高分的节点数目题目算法设计深度优先搜索 题目
传送门https://leetcode.cn/problems/count-nodes-with-the-highest-score/ 算法设计深度优先搜索
这题的核心是计算分数。
一个节点的分数 左子树节点数 × 右子树节点数 × 除自己外其他节点数。如下图 删除某个节点之后最多会把二叉树分割成 三个部分 左子树、右子树、父节点及父节点的另一半子树除自己外其他节点个数。
使用 DFS 算出左子树节点数、右子树节点数。
因为知道树节点的总数再计算除自己外其他节点个数。
除自己外其他节点个数 总数 - 1 - 左子树节点数 - 右子树节点数。
具体怎么解呢
一个节点的分数 左子树节点数 × 右子树节点数 × 除自己外其他节点数 一是需要清晰左子树节点数、右子树节点数再通过总数 - 左右子树数 - 1得到除自己外其他节点数 二是三个数量都有了之后相乘就是删除这个节点之后的分数当然这里有可能三个部分中缺失一部分或者两部分缺失的部分用 1 来代替去相乘。 最终表达式一个节点的分数 左子树节点数 × 右子树节点数 × (总数 - 左右子树数 - 1)
int dfs(vectorvectorint tree, vectorlong s, int i) { long score 1, sum 1; // 分数节点总数设置为long防止溢出for (int j : tree[i]) { // 遍历i所有子节点int cnt dfs(tree, s, j); // 得出子树节点个数score * cnt, sum cnt; // 计算左右子树的得分同时计算节点总数累计每个子树节点数量和。因为分数等于三块的乘积可同时计算节点数量、分数} s[i] score * (max(1ll, (long)tree.size() - sum)); // 一个节点分数 左子树节点数 × 右子树节点数 × (总数 - 左右子树数 - 1)。1ll是把1改成long long类型return i ! 0 ? sum : count(begin(s), end(s), *max_element(begin(s), end(s))); // *max_element查询最大分数count统计最大分数的个数
}
int countHighestScoreNodes(vectorint parents) { // 题目给的 parents 数组不是树先建树int n parents.size();vectorvectorint tree(n); // 用数组存储树vectorlong s(n); for (int i 1; i n; i) tree[parents[i]].push_back(i); // 根据parents建树tree[i]存储i的子节点return dfs(tree, s, 0); // 在图上dfs计算分数
}
