难度: Medium
给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
示例 1：
输入：root = [3,1,4,3,null,1,5] 输出：4 解释：图中蓝色节点为好节点。 根节点 (3) 永远是个好节点。 节点 4 -> (3,4) 是路径中的最大值。 节点 5 -> (3,4,5) 是路径中的最大值。 节点 3 -> (3,1,3) 是路径中的最大值。
示例 2：
输入：root = [3,3,null,4,2] 输出：3 解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。
示例 3：
输入：root = [1] 输出：1 解释：根节点是好节点。
提示：
[1, 10^5] 。[-10^4, 10^4] 。运行时间: 102 ms
内存: 29.8 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def goodNodes(self, root: TreeNode) -> int:
res = 0
def dfs(root, mx):
if not root:
return
if root.val >= mx:
nonlocal res
res += 1
mx = root.val
dfs(root.left, mx)
dfs(root.right, mx)
dfs(root, -inf)
return res
本题解采用了深度优先搜索（DFS）的方法来遍历二叉树中的所有节点，并在每个节点处检查其是否为好节点。定义'好节点'为该节点的值不小于从根到该节点路径上的任何节点的值。DFS在每次递归调用时，将当前路径上的最大值作为参数传递，这样可以在遍历到每个节点时，直接与这个最大值进行比较。如果当前节点的值大于或等于这个最大值，那么此节点被认为是好节点，并更新计数器和路径上的最大值。递归遍历左右子树直到所有节点都被访问。
时间复杂度: O(n)
空间复杂度: O(h)，其中h为树的高度
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def goodNodes(self, root: TreeNode) -> int:
res = 0 # 初始化好节点计数器
def dfs(root, mx):
if not root:
return # 如果节点为空，结束当前递归
if root.val >= mx:
nonlocal res
res += 1 # 如果当前节点的值大于等于路径最大值，则计数器加一
mx = root.val # 更新路径上的最大值
dfs(root.left, mx) # 递归访问左子树，路径最大值为mx
dfs(root.right, mx) # 递归访问右子树，路径最大值为mx
dfs(root, -float('inf')) # 从根节点开始递归，初始化路径最大值为负无穷
return res # 返回总的好节点数
在深度优先搜索（DFS）中选择负无穷大作为初始的最大值参数，是为了确保根节点能够被计算为好节点。由于好节点的定义是节点的值不小于从根到该节点路径上的任何节点的值，使用负无穷大作为起始比较基准可以保证根节点的值总是大于或等于这个初始值。这样，无论根节点的实际值是多少，它都会被正确地识别为好节点。
如果已知二叉树的所有节点值都是非负的，则可以将初始最大值设为0而不是负无穷大。这是因为非负值意味着树中的最小可能节点值为0。这样做可以稍微简化比较过程，但实际上对算法的性能提升不大，因为关键操作是节点值的比较，无论比较的是0还是负无穷大，操作的复杂度是相同的。
在递归调用`dfs(root.left, mx)`和`dfs(root.right, mx)`时，可以直接使用`mx`而不是更新后的最大值，因为每个节点路径都是独立的。当我们从一个父节点向下递归到其子节点时，子节点只需与其父节点路径上的最大值进行比较。这保持了递归过程中路径上的最大值的正确性，而不需要在每次递归时都更新传递给左右子树的最大值。每个节点都在其特定路径上独立地考虑，确保了算法的正确性。
在二叉树中，如果存在节点值相等的情况，根据好节点的定义，这些节点仍然可以被视为好节点，只要它们的值不小于从根到该节点路径上的任何其他节点的值。因此，即使两个连续的节点具有相同的值，只要该值不小于任何先前节点的值，这两个节点都可以被算作好节点。这种处理方式确保了算法的包容性和正确性，即使在节点值相等的情况下也能正确地统计好节点的数量。