Open godkingjay opened 10 months ago
Count Nodes Equal to Average of Subtree Solution::- class Solution { public: int result;
pair<int, int> solve(TreeNode* root) {
if(!root)
return {0, 0};
pair<int, int> l = solve(root->left);
pair<int, int> r = solve(root->right);
int leftSum = l.first;
int leftCount = l.second;
int rightSum = r.first;
int rightCount = r.second;
int SUM = leftSum + rightSum + root->val;
int COUNT = leftCount + rightCount + 1;
int avg = SUM/COUNT;
if(avg == root->val) {
result++;
}
return {SUM, COUNT};
}
int averageOfSubtree(TreeNode* root) {
result = 0;
solve(root);
return result;
}
};
Approach-Doing postorder traversal
Difficulty
Medium
Problem Description
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:
n
elements is the sum of then
elements divided byn
and rounded down to the nearest integer.root
is a tree consisting ofroot
and all of its descendants.Example 1:
Example 2:
Constraints:
[1, 1000]
.0 <= Node.val <= 1000
Link
https://leetcode.com/problems/count-nodes-equal-to-average-of-subtree/