👨‍💻 Simple C++ Solution | Explained in Comments ✏️ | O(n) Solution
Approach: \nThe approach involves a recursive function, calculateSubtreeSum, that calculates the sum of values and the number of nodes in a subtree. It does thi
# Approach: \nThe approach involves a recursive function, calculateSubtreeSum, that calculates the sum of values and the number of nodes in a subtree. It does this by visiting each node in a bottom-up manner. If a node satisfies the condition (its value equals the average), it increments the count. The averageOfSubtree function initiates this process and returns the final count.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(1), No extra space is used , except for recursive stack space\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  int count = 0;  // Initialize a variable to count valid subtrees.\n\n  // A helper function to calculate the sum and count of valid subtrees.\n  pair<int, int> solve(TreeNode* root) {\n      // If the node is null, return 0 for both sum and count.\n    if (root == nullptr) return {0, 0};  \n    int subtreeSum = root->val;  // Initialize the sum with the current node\'s value.\n    int subtreeNodeCount = 1;    // Initialize the node count with 1 for the current node.\n\n    // Recursively calculate the sum and node count for the left and right subtrees.\n    pair<int, int> leftSubtree = solve(root->left);\n    pair<int, int> rightSubtree = solve(root->right);\n\n    // Update the sum and node count with values from left and right subtrees.\n    subtreeSum += leftSubtree.first + rightSubtree.first;\n    subtreeNodeCount += leftSubtree.second + rightSubtree.second;\n\n    // Check if the current node satisfies the condition (value is equal to the average).\n    if (root->val == (subtreeSum / subtreeNodeCount)) {\n      count++;  // Increment the count if the condition is met.\n    }\n\n    return {subtreeSum, subtreeNodeCount};\n  }\n\n  int averageOfSubtree(TreeNode* root) {\n    pair<int, int> result = solve(root);  // Calculate the sum and count.\n    return count;  // Return the count of valid subtrees.\n  }\n};\n\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']