本文主要是介绍Leetcode3249. 统计好节点的数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Every day a Leetcode
题目来源：3249. 统计好节点的数目
解法1：深度优先搜索
建树，然后从根节点 0 开始 DFS 这棵树。
DFS 返回子树大小。
对于节点 x，如果其是叶子节点，或者其所有儿子子树大小都一样，那么答案加一。
代码：
/** @lc app=leetcode.cn id=3249 lang=cpp** [3249] 统计好节点的数目*/// @lc code=start
class Solution
{
public:int countGoodNodes(vector<vector<int>> &edges){int n = edges.size() + 1; // 节点数// 构建邻接表vector<vector<int>> adj(n);for (vector<int> &edge : edges){int u = edge[0], v = edge[1];adj[u].push_back(v);adj[v].push_back(u);}int ans = 0;// parent 为父节点function<int(int, int)> dfs = [&](int u, int parent) -> int{int cnt_sum = 1; // 节点总数，先计入自身int single_cnt = 0;bool valid = true;for (int v : adj[u]){// 规避邻接点中已访问过的父节点，不需要 visited 数组if (v == parent)continue;int cnt = dfs(v, u);cnt_sum += cnt;// 检测子树的节点数量是否相同if (single_cnt == 0)single_cnt = cnt;else if (single_cnt != cnt)valid = false;}ans += valid;return cnt_sum;};dfs(0, -1); // -1 即不存在父节点return ans;}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(n)，其中 n 是数组 edges 的长度。
空间复杂度：O(n)，其中 n 是数组 edges 的长度。
这篇关于Leetcode3249. 统计好节点的数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
