力扣2049:统计最高分的节点数目

2022年03月11日 力扣每日一题

题目

给你一棵根节点为 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 表示一棵二叉树。

Related Topics

• 树
• 深度优先搜索
• 数组
• 二叉树

个人解法

思路：

这题是要返回有 最高得分节点的 数目，那么就要将每一个节点的分数都算一遍，而每一个节点的分数，是由以下几个数的乘积，包括，该节点下左子树中节点的数目、该节点下右子树中节点的数目，以及总节点数-改节点为跟节点的树的节点数。

那么，我的解题步骤如下：

1. 我先根据题目给的parents数组分别统计每个节点的直连子节点，将其存放进map中。

2. 根据map运用递归求出每一个节点做为根节点的子树中的节点数，将其存入counts数组中

3. 接下来遍历求每一个节点的分数，并且记入最大得分及节点的数量

下面是java的代码解法：

class Solution {
    
    // 记录每一个节点作为根节点的子树中节点的数量
    int[] counts;
    public int countHighestScoreNodes(int[] parents) {
    
        int size = parents.length;

        // 记录每个节点的直接子节点
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < size; i++) {
    
            map.put(i, new ArrayList<>());
        }
        for (int i = 1; i < size; i++) {
    
            map.get(parents[i]).add(i);
        }

        // 记录每个子节点为根节点的树中节点数
        counts = new int[size];
        for (int i = 0; i < size; i++) {
    
            if (counts[i] > 0) {
    
                continue;
            }
            counts[i] = dfs(map.get(i), map);
        }

        // 遍历计算每个节点的得分并统计结果
        long mul = 1;
        for (int num : map.get(0)) {
    
            mul *= counts[num];
        }
        int count = 1;
        for (int i = 1; i < size; i++) {
    
            long temp = 1;
            for (int num : map.get(i)) {
    
                temp *= counts[num];
            }
            temp *= (size - counts[i]);
            if (temp > mul) {
    
                mul = temp;
                count = 1;
            } else if (temp == mul) {
    
                count++;
            }
        }
        return count;
    }
    /** * 计算每个节点为根节点的树中节点数 */
    private int dfs(List<Integer> list, Map<Integer, List<Integer>> map) {
    
        if (list.size() == 0) {
    
            return 1;
        }
        int count = 1;
        for (int i : list) {
    
            if (counts[i] > 0) {
    
                count += counts[i];
            } else {
    
                count += dfs(map.get(i), map);
            }
        }
        return count;
    }
}