分析
- 递归遍历：
- 使用深度优先搜索 (DFS) 遍历树中所有节点
- 在遍历过程中，记录从根节点到当前节点路径上的最大值
max_val
- 判断当前节点是否为好节点：
- 如果当前节点的值大于或等于
max_val，说明该节点是好节点，计数器加一，并更新路径上的最大值为当前节点的值
- 继续递归左右子树：
- 对当前节点的左右子树递归调用，传递更新后的
max_val
- 累加结果：
- 将左子树和右子树的好节点数量加上当前节点的结果，返回总计数
时间复杂度
每个节点只访问一次，因此时间复杂度为 O(n)，其中 n 是树中节点的数量
空间复杂度
递归调用栈的空间复杂度为 O(h)，其中 h 是树的高度。在最坏情况下（单链树），空间复杂度为 O(n)
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution
{
public:
int goodNodes(TreeNode* root)
{
// 从根节点开始深度优先搜索，初始路径的最大值为最小整数
return dfs(root, INT_MIN);
}
int dfs(TreeNode* root, int max_val)
{
// 如果节点为空，返回0（没有好节点）
if (!root)
return 0;
int res = 0;
// 判断当前节点是否为好节点
if (root->val >= max_val)
{
res = 1; // 当前节点是好节点
max_val = root->val; // 更新路径上的最大值
}
// 递归左右子树并累加好节点数量
return res + dfs(root->left, max_val) + dfs(root->right, max_val);
}
};
|
