Practice/Meta/Leetcode 2265. Count Nodes Equal to Average of Subtree

Leetcode 2265. Count Nodes Equal to Average of Subtree

CodingMust

Problem

Given the root of a binary tree, return the number of nodes where the node's value equals the average of all values in its subtree.

The average of a subtree is defined as the integer division (floor) of the sum of all node values in that subtree divided by the count of nodes in that subtree. In other words, for a node's subtree: average = floor(sum_of_values / number_of_nodes).

A node's subtree includes the node itself and all of its descendants.

Requirements

1. Count all nodes whose value equals the floored average of their subtree
2. Each node's subtree includes the node itself plus all descendants
3. Use integer division (floor) when calculating averages
4. Return the total count of matching nodes

Constraints

• The number of nodes in the tree is in the range [1, 1000]
• 0 <= Node.val <= 1000
• Time complexity: aim for O(n) where n is the number of nodes
• Space complexity: O(h) for recursion stack where h is tree height

Examples

Example 1:

Input: root = [8] Output: 1 Explanation: The only node has value 8 and its subtree average is 8/1 = 8, so it matches.

Example 2:

` Input: root = [4,8,5,0,1,null,6] Output: 5 Explanation: Tree structure: 4 /
8 5 / \
0 1 6

Node 0: subtree sum = 0, count = 1, average = 0 (matches) Node 1: subtree sum = 1, count = 1, average = 1 (matches) Node 8: subtree sum = 9, count = 3, average = 3 (does not match) Node 6: subtree sum = 6, count = 1, average = 6 (matches) Node 5: subtree sum = 11, count = 2, average = 5 (matches) Node 4: subtree sum = 20, count = 6, average = 3 (does not match)

Total matching nodes: 5 `

Example 3:

Input: root = [1] Output: 1 Explanation: Single node always matches its subtree average.