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

CS-ZH

于 2022-03-11 10:19:32 发布

阅读量335

点赞数

CC 4.0 BY-SA版权

分类专栏：算法文章标签： leetcode 算法数据结构

本文链接：https://blog.csdn.net/code25/article/details/123416849

算法专栏收录该内容

7 篇文章

订阅专栏

该代码实现了一个深度优先搜索算法，用于计算树中具有最高得分的节点数量。算法首先初始化节点列表和最高分计数，然后通过遍历节点构建子节点关系。在深度优先搜索过程中，计算每个节点的分数并更新最高分及其对应的节点数量。最终返回最高分节点的数量。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

class Solution {
    long maxScore = 0; // 记录最高分
    int cnt = 0; // 最高分的节点数目,count的缩写
    int n; // 节点数目
    List<Integer>[] children; // 每个节点的子节点列表

    public int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        children = new List[n]; // 因为要用到n,所以在方法内初始化
        for (int i = 0; i < n; i++) {
            children[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n; i++) {
            int p = parents[i]; // 需要判断父节点是否是-1
            if (p != -1) { // 如果是-1，会超出children数组的边界
                children[p].add(i); // 找到每个节点的所有子节点
            }
        }
        dfs(0); // 深度优先搜索，以返回的是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; // 以当前节点为根的树的节点数目
    }
}