列表

详情


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

给你一棵根节点为 0 的 二叉树 ,它总共有 n 个节点,节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵树,其中 parents[i] 是节点 i 的父节点。由于节点 0 是根,所以 parents[0] == -1 。

一个子树的 大小 为这个子树内节点的数目。每个节点都有一个与之关联的 分数 。求出某个节点分数的方法是,将这个节点和与它相连的边全部 删除 ,剩余部分是若干个 非空 子树,这个节点的 分数 为所有这些子树 大小的乘积 。

请你返回有 最高得分 节点的 数目 。

 

示例 1:

example-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:

example-2

输入:parents = [-1,2,0]
输出:2
解释:
- 节点 0 的分数为:2 = 2
- 节点 1 的分数为:2 = 2
- 节点 2 的分数为:1 * 1 = 1
最高分数为 2 ,有两个节点分数为 2 (分别为节点 0 和 1 )。

 

提示:

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: int countHighestScoreNodes(vector<int>& 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

上一题