💢☠💫Easiest👾Faster✅💯 Lesser🧠 🎯 C++✅Python3🐍✅Java✅C✅Python🐍✅C#✅💥🔥💫Explained☠💥🔥 Beats 100
Intuition\n\n\n\n\n\n\n Describe your first thoughts on how to solve this problem. \njavascript []\n//JavaScript Code\n/**\n * Definition for a binary tree node
# Intuition\n![0ehh83fsnh811.jpg](https://assets.leetcode.com/users/images/b57586fb-9e84-40b1-9a1c-785bb15f2294_1724519585.213553.jpeg)\n![Screenshot 2024-08-24 181607.png](https://assets.leetcode.com/users/images/270a6ea2-a2cc-4e8e-85c5-fb6de0e69ae3_1724519622.3489833.png)\n![Screenshot 2024-08-24 221728.png](https://assets.leetcode.com/users/images/af233000-f049-4f89-9612-87a2a8d45986_1724519878.7303038.png)\n![Screenshot 2024-08-24 223014.png](https://assets.leetcode.com/users/images/deb571da-1b95-4c8c-be4a-9f5ec3ca3935_1724519890.878601.png)\n![Screenshot 2024-08-24 223053.png](https://assets.leetcode.com/users/images/8fdca08b-6b65-4351-a09b-bf4d2979facf_1724519900.7773364.png)\n![Screenshot 2024-08-24 173600.png](https://assets.leetcode.com/users/images/9c4e09c8-d11e-4c48-92be-2b022a97444a_1724519603.5428207.png)\n<!-- Describe your first thoughts on how to solve this problem. -->\n```javascript []\n//JavaScript Code\n/**\n * Definition for a binary tree node.\n * function TreeNode(val, left, right) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.left = (left===undefined ? null : left)\n *     this.right = (right===undefined ? null : right)\n * }\n */\n/**\n * @param {TreeNode} root\n * @return {number}\n */\n/*\nclass Pair{\n    constructor(son, count){\n        this.son = son;\n        this.count = count;\n    }\n}\nvar res = 0\ndfs = (root) =>{\n    if(root === undefined)\n        return new Pair(0, 0)\n    const l = dfs(root.left)\n    const r = dfs(root.right)\n    \n    let sum = root.val + l.son + r.son\n    let height = 1 + l.count + r.count\n    \n    if(Math.floor(sum / height) === root.val)\n        res++\n    \n    return new Pair(sum, height)\n}\n*/\nvar averageOfSubtree = function(root) {\n    function traverse(node) {\n        if (!node) \n            return {count: 0, sum: 0, result: 0};\n\n        let left = traverse(node.left);\n        let right = traverse(node.right);\n\n\n        const curr = {count: 1 + left.count + right.count, sum: node.val + left.sum + right.sum, result: left.result + right.result};\n\n        if (Math.floor(curr.sum / curr.count) === node.val)\n            curr.result = (curr.result || 0) + 1;\n        \n        return curr;\n    }\n\n    const {result} = traverse(root);\n    return result;\n};\n```\n```C++ []\n//C++ Code\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),\n * right(right) {}\n * };\n */\nclass Solution {\n    int cnt = 0;\n    int sum;\n\nprivate:\n    int sumOfNodes(TreeNode* root) {\n        if (!root)\n            return 0;\n\n        sum += root->val;\n        sumOfNodes(root->left);\n        sumOfNodes(root->right);\n\n        return sum;\n    }\n    int heightOfNodes(TreeNode* root) {\n        if (!root)\n            return 0;\n        int l = heightOfNodes(root->left);\n        int r = heightOfNodes(root->right);\n        return l + r + 1;\n    }\n\npublic:\n    int averageOfSubtree(TreeNode* root) {\n        if (!root)\n            return 0;\n        sum = 0;\n        int s = sumOfNodes(root);\n        int h = heightOfNodes(root);\n        if ((sum / h) == root->val)\n            ++cnt;\n        \n        averageOfSubtree(root->left);\n        averageOfSubtree(root->right);\n\n        //cout << s << endl;\n        //cout << height << endl;\n        return cnt;\n    }\n};\n```\n```Python3 []\n#Python3 Code\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: TreeNode) -> int:\n        ans = 0\n        def helper(node, sun, height):\n            nonlocal ans\n            if not node:\n                return (0, 0)\n            \n            Left = helper(node.left , sun, height)\n            Right = helper(node.right, sun, height)\n            \n            sun = Left[0] + Right[0] + node.val\n            height = 1 + Left[1] + Right[1]\n            \n            if sun // height == node.val:\n                ans += 1\n            return (sun, height)\n        \n        helper(root, 0, 0)\n        return ans\n```\n```Java []\n//Java Code\n/**\n * Definition for a binary tree node.\n * public 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 */\nclass Solution {\n    int cnt = 0;\n    private int sumOfNodes(TreeNode root){\n        if(root == null)\n            return 0;\n        return root.val + sumOfNodes(root.left) + sumOfNodes(root.right);\n    }\n    \n    private int heightOfNodes(TreeNode root){\n        if(root == null)\n            return 0;\n        \n        return 1 + heightOfNodes(root.left) + heightOfNodes(root.right);\n    }\n    public int averageOfSubtree(TreeNode root) {\n        if(root == null)\n            return 0;\n\n        int s = sumOfNodes(root);\n        int h = heightOfNodes(root);\n        \n        if(s / h == root.val)\n            cnt++;\n        \n        averageOfSubtree(root.left);\n        averageOfSubtree(root.right);\n        \n        return cnt;\n    }\n}\n```\n```C []\n//C Code\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     struct TreeNode *left;\n *     struct TreeNode *right;\n * };\n */\n\ntypedef struct Pair{\n    int son;\n    int count;\n}pair;\n\npair* init(int son, int count){\n    pair* p = (pair*)malloc(sizeof(pair));\n    p->son = son;\n    p->count = count;\n    return p;\n}\n\npair* dfs(struct TreeNode* root, int* cnt){\n    if(!root){\n        return init(0, 0);\n    }\n    \n    pair* Left = dfs(root->left, cnt);\n    pair* Right = dfs(root->right, cnt);\n    \n    int sum = root->val + Left->son + Right->son;\n    int height = 1 + Left->count + Right->count;\n    \n    if(root->val == sum / height)\n        (*cnt)++;\n    \n    return init(sum, height);\n}\n\nint averageOfSubtree(struct TreeNode* root) {\n    int cnt = 0;\n    dfs(root, &cnt);\n    return cnt;\n}\n```\n```Python []\n#Python Code\n# Definition for a binary tree node.\n# class TreeNode(object):\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution(object):\n    def averageOfSubtree(self, root):\n        """\n        :type root: TreeNode\n        :rtype: int\n        """\n         # Helper function for traversal\n        def traverse(root, count):\n        \n            # Base Case\n            if not root: return [0,0]\n        \n            # Traverse left and get the total sum and count of nodes\n            leftSum, leftCount = traverse(root.left, count)\n    \n            # Traverse right\n            rightSum, rightCount = traverse(root.right, count)\n        \n            # Check the condition\n            if (leftSum + root.val + rightSum) // (leftCount + 1 + rightCount) == root.val: count[0] += 1\n            \n            # Return the data for current subtree back\n            return [leftSum + root.val + rightSum, leftCount + 1 + rightCount]\n    \n    \n        # To keep track of the count of nodes\n        count = [0]\n        \n        # Call the helper function\n        traverse(root, count)\n        \n        # Return the count of nodes\n        return count[0]\n             \n```\n```C# []\n//C# Code\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     public int val;\n *     public TreeNode left;\n *     public TreeNode right;\n *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\npublic class Solution {\n    public int count = 0;\n\n    public (int sum, int count) SumSub(TreeNode root) {\n        if (root == null) \n            return (0, 0);\n\n        var left = SumSub(root.left);\n        var right = SumSub(root.right);\n\n        int sum = root.val + left.sum + right.sum;\n        int totalCount = 1 + left.count + right.count;\n\n        if (root.val == sum / totalCount)\n            count++;\n        return (sum, totalCount);\n    }\n\n    public int AverageOfSubtree(TreeNode root) {\n        SumSub(root);\n        return count;\n    }\n}\n```\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n     O(N) --> C Code\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n     O(N) --> C Code\n# Code\n![th.jpeg](https://assets.leetcode.com/users/images/794d2b38-b797-4024-a2d0-4781328017ff_1724520243.851931.jpeg)\n
['Tree', 'Depth-First Search', 'C', 'Binary Tree', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']