Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2265.html
2265. Count Nodes Equal to Average of Subtree
 Difficulty: Medium.
 Related Topics: Tree, DepthFirst Search, Binary Tree.
 Similar Questions: Maximum Average Subtree, Insufficient Nodes in Root to Leaf Paths, Count Nodes Equal to Sum of Descendants.
Problem
Given the root
of a binary tree, return the number of nodes where the value of the node is equal to the **average of the values in its subtree**.
Note:

The average of
n
elements is the sum of then
elements divided byn
and rounded down to the nearest integer. 
A subtree of
root
is a tree consisting ofroot
and all of its descendants.
Example 1:
Input: root = [4,8,5,0,1,null,6]
Output: 5
Explanation:
For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4.
For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5.
For the node with value 0: The average of its subtree is 0 / 1 = 0.
For the node with value 1: The average of its subtree is 1 / 1 = 1.
For the node with value 6: The average of its subtree is 6 / 1 = 6.
Example 2:
Input: root = [1]
Output: 1
Explanation: For the node with value 1: The average of its subtree is 1 / 1 = 1.
Constraints:

The number of nodes in the tree is in the range
[1, 1000]
. 
0 <= Node.val <= 1000
Solution (Java, C++, Python)

/** * 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 { private 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 currsum = left[0] + right[0] + node.val; int currcount = left[1] + right[1] + 1; if (currsum / currcount == node.val) { ++ans; } return new int[] {currsum, currcount}; } }

Todo

# 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: Optional[TreeNode]) > int: def dfs(root): if root is None: return 0, 0 ls, ln = dfs(root.left) rs, rn = dfs(root.right) s = ls + rs + root.val n = ln + rn + 1 if s // n == root.val: nonlocal ans ans += 1 return s, n ans = 0 dfs(root) return ans ############ # 2265. Count Nodes Equal to Average of Subtree # https://leetcode.com/problems/countnodesequaltoaverageofsubtree/ # 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: Optional[TreeNode]) > int: res = 0 def go(node): if not node: return (0, 0) lCount, lValues = go(node.left) rCount, rValues = go(node.right) nodeCount, nodeValues = 1 + lCount + rCount, node.val + lValues + rValues average = nodeValues // nodeCount if node.val == average: nonlocal res res += 1 return (nodeCount, nodeValues) go(root) return res
Explain:
nope.
Complexity:
 Time complexity : O(n).
 Space complexity : O(n).