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

链接：2049.统计最高分的节点数目
难度：Medium
标签：树、深度优先搜索、数组、二叉树
简介：请你返回有 最高得分 节点的 数目 。

题解 1 - cpp

• 编辑时间：2022-03-11
• 执行用时：128ms
• 内存消耗：79.6MB
• 编程语言：cpp
• 解法介绍：统计每个点的父节点，左子树个数，右子树个数。

class Solution {
   public:
    struct node {
        int parent, left, right, lcnt, rcnt;
    };
    // ans
    int ans = 0;
    long long maxnum = -1;
    void setAns(long long num) {
        if (num >= maxnum) {
            if (num > maxnum) ans = 0;
            ans++;
            maxnum = num;
        }
    }
    int countHighestScoreNodes(vector<int>& parents) {
        int n = parents.size();
        vector<node> list(n);
        // init
        for (int i = 0; i < n; i++) {
            list[i].parent = parents[i];
            list[i].left = list[i].right = -1;
            list[i].lcnt = list[i].rcnt = 0;
        }
        // load
        for (int i = 1; i < n; i++) {
            if (list[list[i].parent].left == -1)
                list[list[i].parent].left = i;
            else
                list[list[i].parent].right = i;
        }
        // check
        int sum = check(list, 0);
        // res
        for (int i = 1; i < n; i++) {
            if (list[i].lcnt == 0 && list[i].rcnt == 0) {
                setAns((long long)list[0].lcnt + list[0].rcnt);
                continue;
            }
            setAns((long long)format(sum - 1 - list[i].lcnt - list[i].rcnt) *
                   format(list[i].lcnt) * format(list[i].rcnt));
        }
        // res0
        setAns((long long)format(list[0].lcnt) * format(list[0].rcnt));
        return ans;
    }
    int check(vector<node>& list, int node) {
        int ans = 0;
        if (list[node].left != -1) {
            list[node].lcnt = check(list, list[node].left);
            ans += list[node].lcnt;
        }
        if (list[node].right != -1) {
            list[node].rcnt = check(list, list[node].right);
            ans += list[node].rcnt;
        }
        return ans + 1;
    }
    int format(int num) { return num == 0 ? 1 : num; }
};