✅ Beats 90.78% 🔥 || DFS 🚀 || Easiest Explanation 💡
\n\n# Intuition:\nHere we are using DFS to traverse the tree and for each node we are calculating the sum of the subtree and the count of the nodes in the subtr
![image.png](https://assets.leetcode.com/users/images/0bd4c280-5db9-4f1e-aa73-209f40decba6_1698889938.1393106.png)\n\n# Intuition:\n**Here we are using DFS to traverse the tree and for each node we are calculating the sum of the subtree and the count of the nodes in the subtree. If the average of the subtree is equal to the value of the node then we increment the result by 1.  We are using a global variable to store the result.**\n\n# Approach: DFS\n1. Initialize the result to 0.\n2. Define a function dfs which takes a node as an argument.\n3. If the node is None then return 0,0.\n4. Call the dfs function recursively on the left and right subtree and store the sum and count of the nodes.\n5. Calculate the sum and count of the current node by adding the value of the node with the sum and count of the left and right subtree.\n6. If the average of the subtree is equal to the value of the node then increment the result by 1.\n7. Return the sum and count of the current node.\n8. Call the dfs function on the root node.\n9. Return the result.\n\n# Complexity Analysis:\n- Time Complexity: **O(N)**, where N is the number of nodes in the tree.\n- Space Complexity: **O(H)**, where H is the height of the tree.\n# Code\n``` Python []\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n        result=0\n\n        def dfs(node):\n            nonlocal result\n            if not node:\n                return 0,0\n            leftSum,leftCount=dfs(node.left)\n            rightSum,rightCount=dfs(node.right)\n            curr_sum=node.val+leftSum+rightSum\n            curr_count=1+leftCount+rightCount\n            if curr_sum//curr_count==node.val:\n                result+=1\n            return curr_sum,curr_count\n        \n        dfs(root)\n        return result \n```\n``` Java []\n/**\n * Definition for a binary tree node.\n * class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\n\nclass Solution {\n    int result = 0;\n    \n    public int averageOfSubtree(TreeNode root) {\n        dfs(root);\n        return result;\n    }\n\n    private int[] dfs(TreeNode node) {\n        if (node == null) {\n            return new int[]{0, 0};\n        }\n\n        int[] left = dfs(node.left);\n        int[] right = dfs(node.right);\n\n        int sum = left[0] + right[0] + node.val;\n        int count = left[1] + right[1] + 1;\n\n        if (sum / count == node.val) {\n            result++;\n        }\n\n        return new int[]{sum, count};\n    }\n}\n```\n``` C++ []\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 val) : val(val), left(nullptr), right(nullptr) {}\n *     TreeNode(int val, TreeNode* left, TreeNode* right) : val(val), left(left), right(right) {}\n * };\n */\n\nclass Solution {\nprivate:\n    int result = 0;\n    \npublic:\n    int averageOfSubtree(TreeNode* root) {\n        dfs(root);\n        return result;\n    }\n\n    vector<int> dfs(TreeNode* node) {\n        if (node == nullptr) {\n            return {0, 0};\n        }\n\n        vector<int> left = dfs(node->left);\n        vector<int> right = dfs(node->right);\n\n        int sum = left[0] + right[0] + node->val;\n        int count = left[1] + right[1] + 1;\n\n        if (sum / count == node->val) {\n            result++;\n        }\n\n        return {sum, count};\n    }\n};\n```\n![image.png](https://assets.leetcode.com/users/images/dc83a943-2164-4d47-ad51-d345e03dc197_1698890289.5112538.png)\n
['Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3']