3249. 统计好节点的数目

题解

class Solution {
public:
    int countGoodNodes(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        int ans = 0;
        auto dfs = [&](auto&& dfs, int x, int p) -> int {
            int size = 1, sz0 = 0;
            bool ok = true;
            for (int y : g[x]) {
                if (y == p) {
                    continue;
                }
                int sz = dfs(dfs, y, x);
                if (sz0 == 0) {
                    sz0 = sz;
                } else if (sz != sz0) {
                    ok = false;
                } 
                size += sz;
            }
            ans += ok;
            return size;
        };
        dfs(dfs, 0, -1);
        return ans;
    }
};

思路

DFS

使用 vector<vector> g(n)来存储无向图节点之间的连接

使用dfs从第一个节点开始遍历，参数x为当前节点，p为父结点防止遍历回父结点。只需要对每个子分支遍历记录节点数即可，只要存在不相同，则标记ok为false，表示该节点子树节点个数不相同。