Count Tree Nodes Matching Their Rounded-Down Subtree Average
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
For each node in the binary tree rooted at `root`, take the average of all values in its subtree, including the node itself, and round down. Return how many nodes have a value equal to that rounded average.
```cpp
class Solution {
public:
int averageOfSubtree(TreeNode* root);
};
```
### Examples
**Example 1:**
```text
Input: root = [2,1,3]
Output: 3
Explanation: Both leaves match themselves. The root matches its subtree average (2+1+3)/3 = 2.
```
**Example 2:**
```text
Input: root = [0,4,5]
Output: 2
Explanation: Both leaves qualify. The root average is floor(9/3) = 3, which differs from its value 0.
```
### Constraints
- The tree contains 1 through 1000 nodes.
- `0 <= Node.val <= 1000`.
### Clarifying Questions
- Does a subtree include its root? Yes, along with all descendants.
- How is a fractional average handled? Round it down to an integer. All node values are nonnegative.
- Does a leaf qualify? Yes; its subtree contains only itself.
- Must the tree change? No changes are needed; return a count.
```hint Check the boundary
Try a one-node tree and a parent whose subtree average is fractional.
```
Overview: Count binary-tree nodes whose values equal their rounded-down subtree average, including each node itself and all of its descendants.