Medium

题目描述

有一棵根节点为 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 <= 10^5
  • parents[0] == -1
  • 对于 i != 0 ，有 0 <= parents[i] <= n - 1
  • parents 表示一个有效的二叉树

解题思路

这道题的核心思路是通过深度优先搜索（DFS）计算每个节点的分数，然后找出最高分数及其对应的节点数量。

解题步骤：

  1. 构建邻接表：根据 parents 数组构建树的邻接表表示，便于遍历子节点。

  2. DFS 计算子树大小：对于每个节点，使用 DFS 递归计算以该节点为根的子树大小。这个信息在计算分数时非常重要。

  3. 计算节点分数：对于每个节点，删除该节点后会产生若干个子树：

    • 该节点的所有子树（如果存在）
    • 除去该节点子树后剩余的部分（如果该节点不是根节点）

    节点的分数就是这些子树大小的乘积。

  4. 统计最高分数：遍历所有节点，记录最高分数和达到最高分数的节点数量。

关键点：

  • 对于根节点，删除后只剩下子树
  • 对于非根节点，删除后除了子树，还有"上半部分"（总节点数减去当前子树大小）
  • 使用 DFS 一次遍历就能计算出所有子树大小，时间复杂度为 O(n)

推荐解法： 本解法是最优解，时间复杂度 O(n)，空间复杂度 O(n)。

代码实现

class Solution {
public:
    int countHighestScoreNodes(vector<int>& parents) {
        int n = parents.size();
        vector<vector<int>> children(n);
        
        // 构建邻接表
        for (int i = 1; i < n; i++) {
            children[parents[i]].push_back(i);
        }
        
        vector<int> subtreeSize(n);
        long long maxScore = 0;
        int count = 0;
        
        function<int(int)> dfs = [&](int node) -> int {
            int size = 1;
            long long score = 1;
            
            for (int child : children[node]) {
                int childSize = dfs(child);
                size += childSize;
                score *= childSize;
            }
            
            // 如果不是根节点，还要考虑删除该节点后剩余的上半部分
            if (parents[node] != -1) {
                score *= (n - size);
            }
            
            if (score > maxScore) {
                maxScore = score;
                count = 1;
            } else if (score == maxScore) {
                count++;
            }
            
            return size;
        };
        
        dfs(0);
        return count;
    }
};

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        n = len(parents)
        children = [[] for _ in range(n)]
        
        # 构建邻接表
        for i in range(1, n):
            children[parents[i]].append(i)
        
        max_score = 0
        count = 0
        
        def dfs(node):
            nonlocal max_score, count
            size = 1
            score = 1
            
            for child in children[node]:
                child_size = dfs(child)
                size += child_size
                score *= child_size
            
            # 如果不是根节点，还要考虑删除该节点后剩余的上半部分
            if parents[node] != -1:
                score *= (n - size)
            
            if score > max_score:
                max_score = score
                count = 1
            elif score == max_score:
                count += 1
            
            return size
        
        dfs(0)
        return count

public class Solution {
    public int CountHighestScoreNodes(int[] parents) {
        int n = parents.Length;
        var children = new List<int>[n];
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        
        // 构建邻接表
        for (int i = 1; i < n; i++) {
            children[parents[i]].Add(i);
        }
        
        long maxScore = 0;
        int count = 0;
        
        int Dfs(int node) {
            int size = 1;
            long score = 1;
            
            foreach (int child in children[node]) {
                int childSize = Dfs(child);
                size += childSize;
                score *= childSize;
            }
            
            // 如果不是根节点，还要考虑删除该节点后剩余的上半部分
            if (parents[node] != -1) {
                score *= (n - size);
            }
            
            if (score > maxScore) {
                maxScore = score;
                count = 1;
            } else if (score == maxScore) {
                count++;
            }
            
            return size;
        }
        
        Dfs(0);
        return count;
    }
}

var countHighestScoreNodes = function(parents) {
    const n = parents.length;
    const children = Array(n).fill(null).map(() => []);
    
    for (let i = 1; i < n; i++) {
        children[parents[i]].push(i);
    }
    
    const subtreeSizes = new Array(n);
    
    function dfs(node) {
        let size = 1;
        for (const child of children[node]) {
            size += dfs(child);
        }
        subtreeSizes[node] = size;
        return size;
    }
    
    dfs(0);
    
    let maxScore = 0;
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        let score = 1;
        
        for (const child of children[i]) {
            score *= subtreeSizes[child];
        }
        
        const parentSubtreeSize = n - subtreeSizes[i];
        if (parentSubtreeSize > 0) {
            score *= parentSubtreeSize;
        }
        
        if (score > maxScore) {
            maxScore = score;
            count = 1;
        } else if (score === maxScore) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个节点访问一次进行DFS遍历
空间复杂度O(n)邻接表存储和递归调用栈的空间开销

相关题目