Leetcode3249：统计好节点的数目

题目描述：

现有一棵 无向 树，树中包含 n 个节点，按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。

如果一个节点的所有子节点为根的子树

 包含的节点数相同，则认为该节点是一个 好节点。

返回给定树中 好节点 的数量。

子树 指的是一个节点以及它所有后代节点构成的一棵树。

代码思路：

这段代码定义了一个名为 Solution 的类，其中包含一个名为 countGoodNodes 的公有成员函数。该函数的目的是计算在一个无向图中“好节点”的数量。一个节点被认为是“好节点”，如果从该节点出发的所有子节点（直接连接的节点）都具有相同的子树节点数（包括自身）。这里的无向图通过边集 edges 表示，其中 edges 是一个二维向量，每个元素是一对整数，代表图中的一条边连接的两个节点。

以下是代码的详细思路：

代码实现：

const int maxn=1e5+1;
class Solution {
public:
    int countGoodNodes(vector<vector<int>> &edges) {
        int vis[maxn]={0};
        vector<int> adj[maxn];
        int ans=0;
        for(auto &edge:edges)
        {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        auto dfs=[&](auto &dfs,int root)
        {
            if(adj[root].empty())
            {
                ans++;
                return 1;
            }
            int sum=1,flag=1,flag2=0,a=0;
            for(int i=0;i<adj[root].size();i++)
            {
                if(vis[adj[root][i]]==0)
                {
                    vis[adj[root][i]]=1;
                    int b=dfs(dfs,adj[root][i]);;
                    if(flag2==0)
                    {
                        a=b;
                        flag2=1;
                    }
                    sum+=b;
                    if(a!=b)
                    {
                        flag=0;
                    }
                }
            }
            if(flag==1)
            {
                ans++;
            }
            return sum;
        };
        vis[0]=1;
        dfs(dfs,0);
        return ans;
    }
};