力扣周赛292--第二题

6057. 统计值等于子树平均值的节点数

题目

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

思路

这题的思路：

• 先深度遍历树，统计出每个节点包含的节点数，并将其放入队列中

• 再深度遍历一次树，这次计算出每个节点的元素和，并从队列中取到该节点的节点数，然后求平均值做判断

代码

Java：

class Solution {
    public int averageOfSubtree(TreeNode root) {
        counts(root);
        sums(root);
        return count;
    }
    Queue<Integer> queue = new LinkedList<>();
    int count = 0;
    private int counts(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int cnt = counts(root.left) + counts(root.right) + 1;
        queue.add(cnt);
        return cnt;
    }
    private int sums(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = root.val;
        sum += sums(root.left);
        sum += sums(root.right);
        if (sum / queue.poll() == root.val) {
            count++;
        }
        return sum;
    }
}