🔥💥 Simple C++ Solution Using Recursion 💥🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves working with a binary tree and finding the number of subtrees in w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves working with a binary tree and finding the number of subtrees in which the `average of values in the subtree` is equal to the value of the `root` of that subtree.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Define a recursive function `countNodes` to `count the number of nodes in a subtree`.\n2. Define another recursive function `totalSum` to calculate the `total sum of values in a subtree`.\n3. In the averageOfSubtree function, for each node:\n    - Calculate the `sum of values` in the current subtree.\n    - Calculate the `total number of nodes` in the current subtree.\n    - Calculate the `average` of values in the current subtree.\n    - If the average is equal to the value of the current node, increment a `counter`.\n    - Recursively call averageOfSubtree on the left and right subtrees.\n4. Finally, return the counter, which represents the` number of subtrees that meet the condition`.\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(h)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n  \nint countNodes(TreeNode*root){\n    if(!root) return 0;\n    return 1 + countNodes(root->left)+ countNodes(root->right);\n}\n\nint totalSum(TreeNode*root){\n    if(!root) return 0;\n    return root->val + totalSum(root->left) + totalSum(root->right);\n}\n int averageOfSubtree(TreeNode* root) {\n      if(!root)   return 0;\n      int sum = root->val + totalSum(root->left) + totalSum(root->right);\n      int totalNodes = 1 + countNodes(root->left) + countNodes(root->right);\n    \n      int avg = floor(sum/totalNodes);\n      if(avg==root->val) {\n        return 1 + averageOfSubtree(root->left) + averageOfSubtree(root->right);\n      }\n      return averageOfSubtree(root->left) + averageOfSubtree(root->right);\n\n    }\n};\n```
['Tree', 'Depth-First Search', 'Recursion', 'Binary Tree', 'C++']