2265.统计值等于子树平均值的节点数：一个深度优先搜索

【LetMeFly】2265.统计值等于子树平均值的节点数：一个深度优先搜索

力扣题目链接：https://leetcode.cn/problems/count-nodes-equal-to-average-of-subtree/

给你一棵二叉树的根节点 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

解题方法：深度优先搜索(DFS)

写一个函数dfs(root)实现以下功能：

1. 计算root为根的子树的节点总数n和节点值总和val；
2. 如果root.val == val / n，则将计数器ans加1。

只需要在root非空时递归计算下左右子树并求和即可。

• 时间复杂度$O(n)$，其中$n=节点数量$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-09-10 14:36:39
 */
typedef pair<int, int> pii;
class Solution {
private:
    int ans;

    pii dfs(TreeNode* root) {
        if (!root) {
            return {0, 0};
        }
        auto [vl, nl] = dfs(root->left);
        auto [vr, nr] = dfs(root->right);
        int val = root->val + vl + vr;
        int n = 1 + nl + nr;
        ans += root->val == val / n;
        return {val, n};
    }
public:
    int averageOfSubtree(TreeNode* root) {
        ans = 0;
        dfs(root);
        return ans;
    }
};

Python

'''
LastEditTime: 2026-09-10 14:53:13
'''
# 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 dfs(self, root: TreeNode) -> tuple[int, int]:
        if not root:
            return 0, 0
        vl, nl = self.dfs(root.left)
        vr, nr = self.dfs(root.right)
        v = root.val + vl + vr
        n = 1 + nl + nr
        self.ans += v // n == root.val
        return v, n

    def averageOfSubtree(self, root: TreeNode) -> int:
        self.ans = 0
        self.dfs(root)
        return self.ans

Java

/*
 * @LastEditTime: 2026-09-10 14:49:28
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
record Result (int val, int n) {}

class Solution {
    private int ans;

    private Result dfs(TreeNode root) {
        if (root == null) {
            return new Result(0, 0);
        }
        Result left = dfs(root.left);
        Result right = dfs(root.right);
        int val = root.val + left.val() + right.val();
        int n = 1 + left.n() + right.n();
        if (val / n == root.val) {
            ans++;
        }
        return new Result(val, n);
    }

    public int averageOfSubtree(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }
}

Go

/*
 * @LastEditTime: 2026-09-10 14:41:32
 */
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var ans int

func dfs(root *TreeNode) (int, int) {
    if root == nil {
        return 0, 0
    }
    vl, nl := dfs(root.Left)
    vr, nr := dfs(root.Right)
    v := root.Val + vl + vr
    n := 1 + nl + nr
    if v / n == root.Val {
        ans++
    }
    return v, n
}

func averageOfSubtree(root *TreeNode) int {
    ans = 0
    dfs(root)
    return ans
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源