Easy C++ Code With Explaination
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nThe below function is a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe below function is a recursive function that calculates and returns the number of nodes in the subtree rooted at a given TreeNode. It does this by traversing the left and right subtrees and adding 1 for the current node.\n\nThe solve function is the main recursive function for solving the problem. It takes two parameters: a reference to a TreeNode pointer and a reference to an integer ans (which will store the count of valid subtrees). This function is used to traverse the binary tree.\n\na. If the current node is null (i.e., there is no subtree to process), it returns 0.\n\nb. It recursively calls solve on the left and right subtrees and stores the result in variable s.\n\nc. It calculates the number of nodes in the current subtree (including the current node) by calling the below function and stores it in variable c.\n\nd. It adds the value of the current node to the s.\n\ne. It checks if the average of the subtree (sum of node values divided by the number of nodes) is equal to the value of the root node. If it is, it increments the ans.\n\nf. Finally, it returns s, which is the sum of values in the current subtree.\n\n# Complexity\n- Time complexity:O(n*height) = O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(1) \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\n\n    int below(TreeNode* root){\n        if(!root)\n        return 0;\n\n        return 1+below(root->left)+below(root->right);\n    } \n\n    int solve(TreeNode* &root,int &ans){\n        if(!root){\n        return 0;\n        }\n\n        int s=0;\n        s+=solve(root->left,ans);\n        // c=0;\n        s+=solve(root->right,ans);\n\n        int c = below(root);\n\n        s+=root->val;\n\n        if(s/c == root->val){\n        ans++;\n        }\n        return s;\n    }\n\n\n    int averageOfSubtree(TreeNode* root) {\n        if(!root)\n        return 0;\n\n        int ans=0;\n        solve(root,ans);\n\n        return ans;\n    }\n};\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']