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 the n elements divided by n and rounded down to the nearest integer.
	A subtree of root is a tree consisting of root and all of its descendants.


&nbsp;
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.


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 1000].
	0 &lt;= Node.val &lt;= 1000


class Solution:
    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
        
        
        def calculate_average(root):
            if root:
                self.summ+=root.val
                self.nodecount+=1
                calculate_average(root.left)
                calculate_average(root.right)
        
        
        def calculate_for_each_node(root):
            if root:
                self.summ = 0
                self.nodecount = 0
                calculate_average(root)
                if ((self.summ)//(self.nodecount)) == root.val:
                    self.count+=1 
                calculate_for_each_node(root.left)
                calculate_for_each_node(root.right)
                
                
        self.count = 0
        calculate_for_each_node(root)       
        return self.count
class Solution {
    int res = 0;
    public int averageOfSubtree(TreeNode root) {
        dfs(root);
        return res;
    }
    
    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) {
            res++;
        }
            
        return new int[] {currSum, currCount};
    }
}
class Solution {
public:
    pair<int,int> func(TreeNode* root,int &ans){
        if(!root)return {0,0};
        auto p1=func(root->left,ans);
        auto p2=func(root->right,ans);
        int avg=(root->val+p1.first+p2.first)/(p1.second+p2.second+1);
        if(avg==root->val)ans++;
        return {root->val+p1.first+p2.first,p1.second+p2.second+1};
    }
    int averageOfSubtree(TreeNode* root) {
        int ans=0;
        func(root,ans);
        return ans;
    }
};
var averageOfSubtree = function(root) {
    let result = 0;
    
    const traverse = node => {
        if (!node) return [0, 0];
        
        const [leftSum, leftCount] = traverse(node.left);
        const [rightSum, rightCount] = traverse(node.right);
        
        const currSum = node.val + leftSum + rightSum;
        const currCount = 1 + leftCount + rightCount;
        
        if (Math.floor(currSum / currCount) === node.val) result++;
        
        return [currSum, currCount];
    };
    
    traverse(root);
    return result;
};
Count Nodes Equal to Average of Subtree