Beats 100% || EASY C++ SOLUTION using recursion
Intuition\n Describe your first thoughts on how to solve this problem. \n \n# Approach\n Describe your approach to solving the problem. \nUse recursion \n# Comp
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n \n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse recursion \n# Complexity\n- Time complexity:\n- O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(height of tree)\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 {\n    pair<int,int> solve(TreeNode* root,int& count){\n        if(root==NULL){\n            return {0,0};\n        }\n         pair<int,int> left=solve(root->left,count);\n         pair<int,int> right=solve(root->right,count);\n        int sum= root->val + left.first + right.first;\n        int curr_count= 1+ left.second + right.second;\n        if(sum / curr_count==root->val){\n            count++;\n        }\n        return {sum,curr_count};\n    }\npublic:\n    int averageOfSubtree(TreeNode* root) {\n        int result=0;\n        solve(root,result);\n        return result;\n        }\n};\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']