Easy C++ code || Optimization from O(n^2) to O(n)
Solving by brute force,\n\nWe iterate to each and every node by using any traversal (preorder, postorder, inorder). I used preorder. \nFrom each and every node 
Solving by brute force,\n\nWe iterate to each and every node by using any traversal (preorder, postorder, inorder). I used preorder. \nFrom each and every node we calculate sum of its subtree nodes and also maintain a cnt variable to store the no. of nodes, so that we can calculate average.\nIf average is equal to value of the root, we increment the ans.\n**Time complexity : O(n^2)**\n\n```\nclass Solution {\npublic:\n    int ans = 0;\n    int sum(TreeNode* root, int& cnt){\n        if(root==NULL) return 0;\n        cnt++;\n        int left = sum(root->left,cnt);\n        int right = sum(root->right,cnt);\n        return (root->val + left + right);\n    }\n    void solve(TreeNode* root){\n        if(root==NULL) return;\n        int cnt = 0;\n        int avg = (sum(root,cnt))/cnt;\n        if(avg==root->val) ans++;\n        solve(root->left);\n        solve(root->right);\n    }\n    int averageOfSubtree(TreeNode* root) {\n        ans = 0;\n        solve(root);\n        return ans;\n    }\n};\n```\n\n**Optimization: **\n\nBefore we calculated the sum for every sub tree.\nHere we do a postorder traversal, we will calculate the sum of nodes in left sub tree and cnt of nodes in left subtree , as well as for right subtree and use this to root.\n**Time complexity: O(n)**\n```\nclass Solution {\npublic:\n    int ans = 0;\n    pair<int,int> solve(TreeNode* root){\n        if(root==NULL) return {0,0};\n        \n        auto left = solve(root->left);\n        int l_sum = left.first; // sum of nodes present in left sub tree\n        int l_cnt = left.second; // no. of nodes present in left sub tree\n        \n        auto right = solve(root->right);\n        int r_sum = right.first; // sum of nodes present in right sub tree\n        int r_cnt = right.second; // no. of nodes present in left sub tree\n        \n        int sum = root->val + l_sum + r_sum;\n        int cnt = l_cnt + r_cnt + 1;\n        \n        if(root->val == sum/cnt) ans++;\n        return {sum,cnt};\n    }\n    int averageOfSubtree(TreeNode* root) {\n        solve(root);\n        return ans;\n    }\n};\n```
['Recursion']