【LeetCode】统计值等于子树平均值的节点数 Java 题解

作者：Albert

2022 年 7 月 02 日
本文字数：1091 字
阅读完需：约 4 分钟

题目描述

给你一棵二叉树的根节点 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。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/count-nodes-equal-to-average-of-subtree著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是二叉树的题目，题目要求找出并返回满足要求的节点数，要求节点的值等于其子树中值的平均值。
分析之后，需要分别求出当前节点的值和子树的平均值。做树相关的题目，我们通常使用深度优先遍历或者广度优先遍历。具体到这个题目，我们采用数组的形式保存，数组元素 0 表示当前节点的和，数组元素 1 表示当前节点的数目的和。有了这两个参数，我们就可以求平均数了。
具体实现代码如下，供参考。

通过代码

/** * 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; *     } * } */class Solution {    int ans = 0;    public int averageOfSubtree(TreeNode root) {        dfs(root);        return ans;    }
    private int[] dfs(TreeNode node) {        if (node == null) {            return new int[]{0, 0};        }        int[] left = dfs(node.left);        int[] right = dfs(node.right);
        int sum = left[0] + right[0] + node.val;        int nodeNum = left[1] + right[1] + 1;        int avg = sum / nodeNum;        if (avg == node.val) {            ans++;        }
        return new int[]{sum, nodeNum};    } }