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

题目描述

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

解法：DFS

这道题我们先根据二叉树的数组存储转换为邻接表，在每个邻接数组的最后插入了 -1，方便 DFS 返回。那么接下来要做的就是深搜一边二叉树，记录每个节点作为根结点的子树有多少个结点（包括自己），记录在 $f[i]$ 中。接下来，就是删除每个结点，如果当前结点为根节点，那么删除它之后就有两颗子树（如下图删除 0）；如果当前结点不是根节点的话，删除它最多会形成三个部分，两棵子树再加上父节点的那一部分（如下图删除 2）

class Solution {
    
public:int countHighestScoreNodes(vector<int>& parents) {
    int n = parents.size();vector<vector<int>> g(n);for (int i = 1; i < n; i++) g[parents[i]].push_back(i);// 遍历到最后一个结点for (auto node: g)node.push_back(-1);vector<int> f(n, 0);int tmp = dfs(0, g, f);long max = 0;int ans  = 0;for (int i = 0; i < n; i++){
    long cur = 1;for (auto v: g[i]) cur *= f[v];if (i != 0) cur *= n - f[i];if (cur > max)max = cur, ans = 1;else if ( cur == max)ans++;}return ans;}int dfs(int root, vector<vector<int>>& g, vector<int>& f){
    int ans = 1;if (root == -1)  return ans;for (auto v: g[root])ans += dfs(v, g, f);f[root] = ans;return ans;}
};