✅☑[C++/Java/Python/JavaScript] || DFS || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n1. Public Member Variables:\n\n- int count: This variable is used to keep t
# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n**(Also explained in the code)**\n\n1. **Public Member Variables:**\n\n- `int count`: This variable is used to keep track of the count of subtrees that satisfy the condition.\n1. **postOrder Function:**\n\n    - The `postOrder` function takes a pointer to a TreeNode, `root`, as an argument.\n    - It follows a post-order traversal approach, which means it first processes the left and right subtrees before processing the current node.\n    - The function returns a pair of integers, where the first element of the pair represents the sum of all nodes in the subtree, and the second element represents the count of nodes in the subtree.\n    - If the input `root` is `NULL` (i.e., there\'s no node), it returns {0, 0} as the base case.\n    - The function recursively calls itself on the left and right subtrees and stores the results in the `left` and `right` variables.\n    - It calculates `nodeSum` as the sum of values in the left subtree, right subtree, and the value of the current node.\n    - It calculates `nodeCount` as the count of nodes in the left subtree, right subtree, plus 1 for the current node.\n    - If the average of the subtree, calculated as `nodeSum / nodeCount`, is equal to the value of the current node (`root->val`), it increments the `count` variable to indicate that this subtree meets the condition.\n    - The function then returns the pair {nodeSum, nodeCount}.\n1. **averageOfSubtree Function:**\n\n    - The `averageOfSubtree` function takes a TreeNode pointer, `root`, as its argument.\n    - It\'s the main entry point for the user, and it will be used to start the process.\n    - It calls the `postOrder` function to traverse the binary tree rooted at `root` and count the subtrees that satisfy the condition.\n    - Finally, it returns the count of such subtrees as the result.\n\n\n# Complexity\n- *Time complexity:*\n   $$O(n)$$\n    \n\n- *Space complexity:*\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int count = 0;\n    \n    pair<int, int> postOrder(TreeNode* root) {\n        if (root == NULL) {\n            return {0, 0};\n        }\n        \n        // First iterate over left and right subtrees.\n        pair<int, int> left = postOrder(root->left);\n        pair<int, int> right = postOrder(root->right);\n        \n        int nodeSum = left.first + right.first + root->val;\n        int nodeCount = left.second + right.second + 1;\n\n        // Check if the average of the subtree is equal to the node value.\n        if (root->val == nodeSum / (nodeCount)) {\n            count++;\n        }\n        \n        // Return the sum of nodes and the count in the subtree.\n        return {nodeSum, nodeCount};\n    }\n    \n    int averageOfSubtree(TreeNode* root) {\n        postOrder(root);\n        return count;\n    }\n};\n\n\n```\n```C []\n#include <stdlib.h>  // For NULL definition\n\nstruct TreeNode {\n    int val;\n    struct TreeNode* left;\n    struct TreeNode* right;\n};\n\nstruct Pair {\n    int first;\n    int second;\n};\n\nint count = 0;\n\nstruct Pair postOrder(struct TreeNode* root) {\n    struct Pair result = {0, 0};\n\n    if (root == NULL) {\n        return result;\n    }\n\n    // First iterate over left and right subtrees.\n    struct Pair left = postOrder(root->left);\n    struct Pair right = postOrder(root->right);\n\n    int nodeSum = left.first + right.first + root->val;\n    int nodeCount = left.second + right.second + 1;\n\n    // Check if the average of the subtree is equal to the node value.\n    if (root->val == nodeSum / nodeCount) {\n        count++;\n    }\n\n    // Update the result and return it.\n    result.first = nodeSum;\n    result.second = nodeCount;\n    return result;\n}\n\nint averageOfSubtree(struct TreeNode* root) {\n    postOrder(root);\n    return count;\n}\n\n\n\n\n```\n```Java []\nclass TreeNode {\n    int val;\n    TreeNode left;\n    TreeNode right;\n    TreeNode(int x) {\n        val = x;\n    }\n}\n\npublic class Solution {\n    private int count = 0;\n\n    public int averageOfSubtree(TreeNode root) {\n        postOrder(root);\n        return count;\n    }\n\n    private Pair<Integer, Integer> postOrder(TreeNode root) {\n        if (root == null) {\n            return new Pair<>(0, 0);\n        }\n\n        Pair<Integer, Integer> left = postOrder(root.left);\n        Pair<Integer, Integer> right = postOrder(root.right);\n\n        int nodeSum = left.getKey() + right.getKey() + root.val;\n        int nodeCount = left.getValue() + right.getValue() + 1;\n\n        if (root.val == nodeSum / nodeCount) {\n            count++;\n        }\n\n        return new Pair<>(nodeSum, nodeCount);\n    }\n}\n\n\n\n```\n```python3 []\nclass TreeNode:\n    def __init__(self, x):\n        self.val = x\n        self.left = None\n        self.right = None\n\nclass Solution:\n    def __init__(self):\n        self.count = 0\n\n    def postOrder(self, root):\n        if root is None:\n            return 0, 0\n\n        left_sum, left_count = self.postOrder(root.left)\n        right_sum, right_count = self.postOrder(root.right)\n\n        node_sum = left_sum + right_sum + root.val\n        node_count = left_count + right_count + 1\n\n        if root.val == node_sum // node_count:\n            self.count += 1\n\n        return node_sum, node_count\n\n    def averageOfSubtree(self, root):\n        self.postOrder(root)\n        return self.count\n\n\n```\n\n```javascript []\nclass TreeNode {\n    constructor(val) {\n        this.val = val;\n        this.left = this.right = null;\n    }\n}\n\nclass Solution {\n    constructor() {\n        this.count = 0;\n    }\n\n    postOrder(root) {\n        if (root === null) {\n            return [0, 0];\n        }\n\n        const [leftSum, leftCount] = this.postOrder(root.left);\n        const [rightSum, rightCount] = this.postOrder(root.right);\n\n        const nodeSum = leftSum + rightSum + root.val;\n        const nodeCount = leftCount + rightCount + 1;\n\n        if (root.val === Math.floor(nodeSum / nodeCount)) {\n            this.count++;\n        }\n\n        return [nodeSum, nodeCount];\n    }\n\n    averageOfSubtree(root) {\n        this.postOrder(root);\n        return this.count;\n    }\n}\n\n\n```\n\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Tree', 'Depth-First Search', 'C', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript']