难度: Medium
给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。
注意：
n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。root 的 子树 由 root 和它的所有后代组成。示例 1：
输入：root = [4,8,5,0,1,null,6] 输出：5 解释： 对值为 4 的节点：子树的平均值 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4 。 对值为 5 的节点：子树的平均值 (5 + 6) / 2 = 11 / 2 = 5 。 对值为 0 的节点：子树的平均值 0 / 1 = 0 。 对值为 1 的节点：子树的平均值 1 / 1 = 1 。 对值为 6 的节点：子树的平均值 6 / 1 = 6 。
示例 2：
输入：root = [1] 输出：1 解释：对值为 1 的节点：子树的平均值 1 / 1 = 1。
提示：
[1, 1000] 内0 <= Node.val <= 1000运行时间: 28 ms
内存: 16.9 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 averageOfSubtree(self, root: TreeNode) -> int:
res = 0
def search(node):
if not node:
return 0, 0
cnt, sums = 1, node.val
if node.left:
t1, t2 = search(node.left)
cnt += t1
sums += t2
if node.right:
t1, t2 = search(node.right)
cnt += t1
sums += t2
if (sums // cnt) == node.val:
nonlocal res
res += 1
return cnt, sums
search(root)
return res
该题解采用了递归的方式进行深度优先搜索(DFS)。对于每个节点，首先递归计算其左右子树内所有节点的值的和以及节点个数。然后，将当前节点的值加到子树的和中，并将节点个数加一，从而获取包括当前节点在内的整个子树的总和和节点个数。接着，计算子树的平均值并向下取整，如果这个值等于当前节点的值，则结果计数器增加。最后，函数返回当前子树的节点数量和值的总和，以供上层节点的计算。
时间复杂度: O(n)
空间复杂度: O(n) in the worst case, O(log(n)) in average case for balanced trees
# 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 averageOfSubtree(self, root: TreeNode) -> int:
res = 0 # 初始化满足条件的节点数量为0
def search(node):
if not node:
return 0, 0 # 如果节点为空，返回节点数和总和都为0
cnt, sums = 1, node.val # 初始化当前节点的计数和总和
if node.left: # 如果有左子节点
t1, t2 = search(node.left) # 递归计算左子树
cnt += t1 # 更新节点总数
sums += t2 # 更新值的总和
if node.right: # 如果有右子节点
t1, t2 = search(node.right) # 递归计算右子树
cnt += t1 # 更新节点总数
sums += t2 # 更新值的总和
if (sums // cnt) == node.val: # 如果当前节点值等于其子树的平均值
nonlocal res
res += 1 # 结果计数器增加
return cnt, sums # 返回当前子树的节点数和总和
search(root) # 从根节点开始搜索
return res # 返回满足条件的节点总数
在计算节点平均值时，使用了整数除法（使用`//`操作符），这种除法操作自动将结果向下舍入到最接近的整数。在Python中，当使用整数除法时，即使结果是负数，也会向下舍入，这是Python整数除法的内置行为。因此，在这种情况下，不需要额外的逻辑来确保结果的正确舍入。
在Python中，整数类型可以自动处理非常大的数值，因为Python的整数类型是动态大小的，可以根据需要自动扩展到更大的位数。因此，在标准的Python实现中，整数溢出是不会发生的。但是，如果这段代码需要在其他可能存在整数溢出的编程语言中实现，可以考虑使用更大的数值类型（如长整型），或者对每次操作后的结果进行检查，确保没有溢出发生。
在递归函数中，当节点为空时返回(0, 0)，是一种处理树遍历中空节点的常见方法。这种设计确保了递归在遇到空的子节点时能正确地处理，并且在求和或计数时不会对结果产生影响。这样可以避免在调用递归函数时进行额外的空检查，简化代码逻辑。但是，这种设计假设了树中不会有节点的值为负数或零，这些情况也需要在实际应用中进行考虑。
使用非局部变量`res`允许在嵌套的递归函数中更新计数器，而不需要将计数结果作为函数的返回值。这种设计简化了函数的返回值结构，使得函数可以专注于计算必要的节点总和和计数。然而，这种设计的缺点是它降低了函数的可重用性和测试性，因为`res`的状态依赖于外部环境，这可能会在并发环境或在需要重新入口递归调用的情况下引发问题。