2049. 統計最高分的節點數目

給你一棵根節點為 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 表示一棵二叉樹。

解題思路

1. 先創建節點類，用來保存二叉樹節點之間的關系以及每個節點下屬節點的數量
2. 遞歸查找每個節點的后代節點的數量，保存在每個節點中
3. 每次刪除某個節點，計算分數的公式為：左子樹的節點個數 * 右子樹的節點個數 * （總節點數-當前子樹節點個數）。遍歷所有節點統計最高得分 節點的 數目 。

代碼

class Node{
public:Node *left,*right;int children;};
class Solution {
public:int countHighestScoreNodes(vector<int>& parents) {map<int,Node*> m;for (int i = 0; i < parents.size(); ++i) {m[i]=new Node();}for (int i = 1; i < parents.size(); ++i) {Node *p=m[parents[i]],*cur=m[i];if (p->left!= nullptr)p->right=cur;else p->left=cur;}this->total=parents.size();count(m[0]);dfs(m[0]);return maxn;}long long  maxx=0;int maxn=0,total;int count(Node *root){if (root== nullptr) return 0;int l=count(root->left),r=count(root->right);return root->children=(1+l+r);}void dfs(Node *root){if (root== nullptr) return ;dfs(root->left);dfs(root->right);long long num=(long long)(root->left== nullptr?1:root->left->children)*(long long)(root->right== nullptr?1:root->right->children)*(long long)max(1,total-root->children);if (num>maxx){maxx=num;maxn=1;}else if (num==maxx){maxn++;}}
};