Medium
题目描述
给定一个有 n 个节点的无向树，节点编号从 0 到 n-1，以节点 0 为根。给定一个长度为 n-1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
如果一个节点的所有子树大小都相同，则该节点是好节点。
返回给定树中好节点的数量。
树的子树是由树中的一个节点及其所有后代组成的树。
示例 1：
输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
输出：7
解释：给定树的所有节点都是好节点。
示例 2：
输入：edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]
输出：6
解释：给定树中有 6 个好节点。
示例 3：
输入：edges = [[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]
输出：12
解释：除了节点 9 之外的所有节点都是好节点。
约束条件：
- 2 <= n <= 10^5
- edges.length == n - 1
- edges[i].length == 2
- 0 <= ai, bi < n
- 输入保证 edges 表示一个有效的树
提示： 使用深度优先搜索（DFS）。
解题思路
解题思路
这道题要求统计树中"好节点"的数量，好节点的定义是：该节点的所有子树大小都相同。
我们可以使用**深度优先搜索（DFS）**来解决这个问题：
构建邻接表：首先根据边的信息构建树的邻接表表示。
DFS遍历：从根节点开始进行DFS遍历，对于每个节点：
- 递归计算其所有子节点的子树大小
- 检查所有子树大小是否相同
- 如果相同（或者是叶子节点），则该节点是好节点
- 返回以当前节点为根的子树大小
判断好节点：一个节点是好节点当且仅当：
- 它是叶子节点（没有子节点），或
- 它的所有子树大小都相同
计算子树大小：每个节点的子树大小等于1（自身）加上所有子树的大小之和。
算法流程：
- 使用DFS后序遍历，先处理子节点再处理当前节点
- 对每个节点收集其所有子树的大小
- 检查这些子树大小是否都相等
- 统计满足条件的节点数量
时间复杂度为O(n)，因为每个节点只访问一次；空间复杂度为O(n)，用于存储邻接表和递归栈。
代码实现
class Solution {
public:
int countGoodNodes(vector<vector<int>>& edges) {
int n = edges.size() + 1;
vector<vector<int>> adj(n);
// 构建邻接表
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
int goodNodes = 0;
function<int(int, int)> dfs = [&](int node, int parent) -> int {
vector<int> childSizes;
int totalSize = 1; // 当前节点自身
// 遍历所有子节点
for (int child : adj[node]) {
if (child != parent) {
int childSize = dfs(child, node);
childSizes.push_back(childSize);
totalSize += childSize;
}
}
// 检查是否为好节点
bool isGood = true;
if (!childSizes.empty()) {
int firstSize = childSizes[0];
for (int size : childSizes) {
if (size != firstSize) {
isGood = false;
break;
}
}
}
if (isGood) {
goodNodes++;
}
return totalSize;
};
dfs(0, -1);
return goodNodes;
}
};
class Solution:
def countGoodNodes(self, edges: List[List[int]]) -> int:
n = len(edges) + 1
adj = [[] for _ in range(n)]
# 构建邻接表
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
good_nodes = 0
def dfs(node, parent):
nonlocal good_nodes
child_sizes = []
total_size = 1 # 当前节点自身
# 遍历所有子节点
for child in adj[node]:
if child != parent:
child_size = dfs(child, node)
child_sizes.append(child_size)
total_size += child_size
# 检查是否为好节点
is_good = True
if child_sizes:
first_size = child_sizes[0]
for size in child_sizes:
if size != first_size:
is_good = False
break
if is_good:
good_nodes += 1
return total_size
dfs(0, -1)
return good_nodes
public class Solution {
public int CountGoodNodes(int[][] edges) {
int n = edges.Length + 1;
List<int>[] adj = new List<int>[n];
// 初始化邻接表
for (int i = 0; i < n; i++) {
adj[i] = new List<int>();
}
// 构建邻接表
foreach (var edge in edges) {
adj[edge[0]].Add(edge[1]);
adj[edge[1]].Add(edge[0]);
}
int goodNodes = 0;
int Dfs(int node, int parent) {
List<int> childSizes = new List<int>();
int totalSize = 1; // 当前节点自身
// 遍历所有子节点
foreach (int child in adj[node]) {
if (child != parent) {
int childSize = Dfs(child, node);
childSizes.Add(childSize);
totalSize += childSize;
}
}
// 检查是否为好节点
bool isGood = true;
if (childSizes.Count > 0) {
int firstSize = childSizes[0];
foreach (int size in childSizes) {
if (size != firstSize) {
isGood = false;
break;
}
}
}
if (isGood) {
goodNodes++;
}
return totalSize;
}
Dfs(0, -1);
return goodNodes;
}
}
var countGoodNodes = function(edges) {
const n = edges.length + 1;
const adj = Array.from({length: n}, () => []);
// 构建邻接表
for (const [a, b] of edges) {
adj[a].push(b);
adj[b].push(a);
}
let goodNodes = 0;
function dfs(node, parent) {
const childSizes = [];
let totalSize = 1; // 当前节点自身
// 遍历所有子节点
for (const child of adj[node]) {
if (child !== parent) {
const childSize = dfs(child, node);
childSizes.push(childSize);
totalSize += childSize;
}
}
// 检查是否为好节点
let isGood = true;
if (childSizes.length > 0) {
const firstSize = childSizes[0];
for (const size of childSizes) {
if (size !== firstSize) {
isGood = false;
break;
}
}
}
if (isGood) {
goodNodes++;
}
return totalSize;
}
dfs(0, -1);
return goodNodes;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n) - 每个节点恰好被访问一次 |
| 空间复杂度 | O(n) - 邻接表存储空间O(n) + 递归栈深度O(n) |