题目

给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。

注意：

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

示例 1： image.png

输入：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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-nodes-equal-to-average-of-subtree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

递归每一个节点，计算该子树的节点个数和节点值的和。如果平均值等于该节点的值，ans加一。

计算父节点的这两个值会依赖子节点返回的值，因此是后序遍历的方式。

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     int ans = 0;
  19.     public int averageOfSubtree(TreeNode root) {
  20.         dfs(root);
  21.         return ans;
  22.     }
  24.     // 返回一个数组，0下标是该子树的节点值总和，1下标是该子树的节点个数
  25.     private int[] dfs(TreeNode root) {
  26.         if (root == null) {
  27.             return new int[]{0, 0};
  28.         }
  29.         int[] left = dfs(root.left);
  30.         int[] right = dfs(root.right);
  31.         int sum = left[0] + right[0] + root.val;
  32.         int cnt = left[1] + right[1] + 1;
  33.         if (sum / cnt == root.val) {
  34.             ans++;
  35.         }
  36.         return new int[]{sum, cnt};
  37.     }
  38. }