O(N) Solution || Simple✅ || Easy to Understand ✅|| beat 100%✅
\n\n# Complexity\n- Time complexity: O(N)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(N)\n Add your space complexity here, e.g. O(n) \n
\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\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    pair<int,int> solve(TreeNode* root, int &cnt){\n        if(root==NULL){\n            return make_pair(0,0);\n        }\n        pair<int,int> left = solve(root->left, cnt);\n        pair<int,int> right = solve(root->right, cnt);\n        \n        pair<int,int>ans;\n        ans.first = root->val + left.first + right.first;\n        ans.second = left.second + right.second + 1;\n        int num = ans.first / ans.second;\n        if(num==root->val) cnt++;\n        return ans;\n    }\n    int averageOfSubtree(TreeNode* root) {\n        int cnt=0;\n        pair<int,int>p = solve(root,cnt);\n        return cnt;\n    }\n};\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']