统计值等于子树平均值的节点数-LeetCode

2265. 统计值等于子树平均值的节点数 - Count Nodes Equal to Average of Subtree

🎯 问题描述（来源于LeetCode）

描述：
给定一棵二叉树的根节点 root，返回满足条件的节点数量：该节点的值等于其子树中所有节点值的平均值。
注意：空节点的平均值未定义，不考虑。

说明：

• n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。
• root 的 子树 由 root 和它的所有后代组成。

示例：

• 示例 1：

输入: root = [4,8,5,0,1,null,6]
输出: 5
解释: 
- 节点 4 的子树和=24，节点数=6，平均值=4，相等 ✅
- 节点 8 的子树和=9，节点数=3，平均值=3，不相等 ❌
- 节点 5 的子树和=5，节点数=1，平均值=5，相等 ✅
- 节点 0 的子树和=0，节点数=1，平均值=0，相等 ✅
- 节点 1 的子树和=1，节点数=1，平均值=1，相等 ✅
- 节点 6 的子树和=6，节点数=1，平均值=6，相等 ✅
总计 5 个节点。

• 示例 2：

输入: root = [1]
输出: 1

💻 解题思路

思路1：后序遍历 + 返回 (总和, 节点数)

算法步骤

1. 全局计数器：ans 记录满足条件的节点数。
2. 定义递归函数 dfs(node)：
   • 返回值：元组 (子树节点值总和, 子树节点个数)。
   • 递归终止：若 node 为 None，返回 (0, 0)。
   • 递归计算左右子树：(left_sum, left_cnt) = dfs(node.left)，(right_sum, right_cnt) = dfs(node.right)。
   • 当前子树的总和：total = node.val + left_sum + right_sum。
   • 当前子树的节点数：cnt = 1 + left_cnt + right_cnt。
   • 判断是否满足条件：node.val == total // cnt（注意：这里使用整数除法，可能不精确，正确做法应为 node.val * cnt == total）。
   • 若满足，ans += 1。
   • 返回 (total, cnt)。
3. 调用 dfs(root)，最终返回 ans。

思路1：代码实现（用户原始代码）

# 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:
        ans = 0
        def dfs(node):
            nonlocal ans
            if not node:
                return (0, 0)
            left_sum, left_cnt = dfs(node.left)
            right_sum, right_cnt = dfs(node.right)
            total = node.val + left_sum + right_sum
            cnt = 1 + left_cnt + right_cnt
            if node.val == total // cnt:   
                ans += 1
            return (total, cnt)
        dfs(root)
        return ans

思路1：📊 性能分析

• 时间复杂度：$O(n)$，每个节点访问一次。
• 空间复杂度：$O(h)$，递归栈深度为树高，最坏 $O(n)$。

思考

• 本题的核心是后序遍历同时获取子树和与节点数，自底向上判断。
• 注意平均值可能是浮点数，使用乘法比较可以避免精度问题。
• 也可以使用迭代后序遍历（栈 + 状态标记）实现，但递归更简洁。