✅ 89.45% Post-order traversal
Intuition\nThe problem asks us to count the number of nodes where the node\'s value is equal to the average of its subtree (including itself). To calculate the 
# Intuition\nThe problem asks us to count the number of nodes where the node\'s value is equal to the average of its subtree (including itself). To calculate the average, we need the sum and count of nodes in the subtree. Our first thought could be to traverse the tree and, for every node, calculate the sum and count of nodes in its subtree and then check if the average matches the node\'s value. However, this would lead to recalculating the sum and count for overlapping subtrees, resulting in a time complexity of $O(n^2)$. Instead, we can optimize our approach to calculate the sum and count while traversing the tree in a single pass.\n\n# Live Coding & More\nhttps://youtu.be/vCD1hGT5e8M?si=JfZ7YX5_VMeOETIa\n\n# Approach\n\nTo solve the problem, we employ a post-order traversal approach. In post-order traversal, the tree is traversed in such a way that we first explore the left subtree, then the right subtree, and finally the node itself. This method is particularly suitable for this problem because, to determine the average value of a subtree rooted at a node, we need information from its left and right subtrees first. \n\n## Base Case\nOur recursive function\'s first duty is to identify if it has reached a leaf node, i.e., a node that doesn\'t have children. If the node being processed is `None`, it indicates that it\'s a leaf, and as such, we return both a sum and count of 0. This is because, for non-existent children of leaf nodes, there\'s no value to add or count to increment.\n\n## Recursive Logic\n\nFor every node in the tree, we perform the following steps:\n\n1. **Left Subtree Processing**:\n   We recursively calculate the sum and count of nodes for the left child of the current node. This gives us the total value of all nodes and the number of nodes in the left subtree.\n\n2. **Right Subtree Processing**:\n   Similarly, we recursively calculate the sum and count of nodes for the right child of the current node. This provides the total value of all nodes and the number of nodes in the right subtree.\n\n3. **Current Node\'s Subtree Calculation**:\n   - **Sum**: To calculate the sum of the values in the subtree rooted at the current node, we add the node\'s own value to the sums from the left and right subtrees. \n   - **Count**: The count of nodes in the subtree rooted at the current node is found by adding 1 (for the current node itself) to the counts from the left and right subtrees.\n   \n4. **Average Comparison**:\n   We check if the average of the subtree rooted at the current node matches the node\'s value. The average is calculated by performing integer division of the sum by the count. If they match, it indicates that the node\'s value is indeed the average of its subtree, and we increment our result counter.\n\n5. **Return Values**:\n   Finally, for the benefit of the parent node in the recursive chain, we return the current node\'s subtree sum and count. This ensures that as the recursion unwinds, each parent node gets the aggregate values of its children and can perform its own calculations.\n\nBy following this approach, the algorithm efficiently traverses the tree, calculating and checking averages in one pass, without needing to revisit nodes or perform redundant calculations.\n\n# Complexity\n- **Time complexity**: $O(n)$. We perform a single traversal of the tree, visiting each node exactly once.\n- **Space complexity**: $O(h)$, where $h$ is the height of the tree. This accounts for the space used by the call stack during the recursive traversal.\n\n\n# Code\n``` Python []\nclass Solution:\n    def averageOfSubtree(self, root: TreeNode) -> int:\n        result = 0\n\n        def traverse(node):\n            nonlocal result\n            \n            if not node:\n                return 0, 0\n            \n            left_sum, left_count = traverse(node.left)\n            right_sum, right_count = traverse(node.right)\n            \n            curr_sum = node.val + left_sum + right_sum\n            curr_count = 1 + left_count + right_count\n            \n            if curr_sum // curr_count == node.val:\n                result += 1\n            \n            return curr_sum, curr_count\n        \n        traverse(root)\n        return result\n```\n``` C++ []\nclass Solution {\npublic:\n    int averageOfSubtree(TreeNode* root) {\n        int result = 0;\n        traverse(root, result);\n        return result;\n    }\n\nprivate:\n    pair<int, int> traverse(TreeNode* node, int& result) {\n        if (!node) return {0, 0};\n        \n        auto [left_sum, left_count] = traverse(node->left, result);\n        auto [right_sum, right_count] = traverse(node->right, result);\n        \n        int curr_sum = node->val + left_sum + right_sum;\n        int curr_count = 1 + left_count + right_count;\n        \n        if (curr_sum / curr_count == node->val) result++;\n        \n        return {curr_sum, curr_count};\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int averageOfSubtree(TreeNode root) {\n        int[] result = new int[1];\n        traverse(root, result);\n        return result[0];\n    }\n\n    private int[] traverse(TreeNode node, int[] result) {\n        if (node == null) return new int[]{0, 0};\n        \n        int[] left = traverse(node.left, result);\n        int[] right = traverse(node.right, result);\n        \n        int currSum = node.val + left[0] + right[0];\n        int currCount = 1 + left[1] + right[1];\n        \n        if (currSum / currCount == node.val) result[0]++;\n        \n        return new int[]{currSum, currCount};\n    }\n}\n```\n``` Go []\nfunc averageOfSubtree(root *TreeNode) int {\n    result := 0\n    traverse(root, &result)\n    return result\n}\n\nfunc traverse(node *TreeNode, result *int) (int, int) {\n    if node == nil {\n        return 0, 0\n    }\n    \n    leftSum, leftCount := traverse(node.Left, result)\n    rightSum, rightCount := traverse(node.Right, result)\n    \n    currSum := node.Val + leftSum + rightSum\n    currCount := 1 + leftCount + rightCount\n    \n    if currSum / currCount == node.Val {\n        *result++\n    }\n    \n    return currSum, currCount\n}\n```\n``` Rust []\nuse std::rc::Rc;\nuse std::cell::RefCell;\nimpl Solution {\n    pub fn average_of_subtree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {\n        fn traverse(node: Option<Rc<RefCell<TreeNode>>>, result: &mut i32) -> (i32, i32) {\n            if let Some(n) = node {\n                let n = n.borrow();\n                let (left_sum, left_count) = traverse(n.left.clone(), result);\n                let (right_sum, right_count) = traverse(n.right.clone(), result);\n                \n                let curr_sum = n.val + left_sum + right_sum;\n                let curr_count = 1 + left_count + right_count;\n                \n                if curr_sum / curr_count == n.val {\n                    *result += 1;\n                }\n                \n                (curr_sum, curr_count)\n            } else {\n                (0, 0)\n            }\n        }\n        \n        let mut result = 0;\n        traverse(root, &mut result);\n        result\n    }\n}\n```\n``` JavaScript []\nvar averageOfSubtree = function(root) {\n    let result = 0;\n    \n    const traverse = node => {\n        if (!node) return [0, 0];\n        \n        const [leftSum, leftCount] = traverse(node.left);\n        const [rightSum, rightCount] = traverse(node.right);\n        \n        const currSum = node.val + leftSum + rightSum;\n        const currCount = 1 + leftCount + rightCount;\n        \n        if (Math.floor(currSum / currCount) === node.val) result++;\n        \n        return [currSum, currCount];\n    };\n    \n    traverse(root);\n    return result;\n};\n```\n``` PHP []\nclass Solution {\n\n    /**\n     * @param TreeNode $root\n     * @return Integer\n     */\n    function averageOfSubtree($root) {\n        $result = 0;\n        $this->traverse($root, $result);\n        return $result;\n    }\n    \n    function traverse($node, &$result) {\n        if ($node === null) return [0, 0];\n        \n        list($leftSum, $leftCount) = $this->traverse($node->left, $result);\n        list($rightSum, $rightCount) = $this->traverse($node->right, $result);\n        \n        $currSum = $node->val + $leftSum + $rightSum;\n        $currCount = 1 + $leftCount + $rightCount;\n        \n        if (intval($currSum / $currCount) == $node->val) $result++;\n        \n        return [$currSum, $currCount];\n    }\n}\n```\n``` C# []\npublic class Solution {\n    public int AverageOfSubtree(TreeNode root) {\n        int result = 0;\n        Traverse(root, ref result);\n        return result;\n    }\n\n    private (int, int) Traverse(TreeNode node, ref int result) {\n        if (node == null) return (0, 0);\n        \n        var (leftSum, leftCount) = Traverse(node.left, ref result);\n        var (rightSum, rightCount) = Traverse(node.right, ref result);\n        \n        int currSum = node.val + leftSum + rightSum;\n        int currCount = 1 + leftCount + rightCount;\n        \n        if (currSum / currCount == node.val) result++;\n        \n        return (currSum, currCount);\n    }\n}\n```\n\n# Performance\n\n| Language   | Execution Time (ms) | Memory Usage |\n|------------|---------------------|--------------|\n| Java       | 0                   | 43.2 MB     |\n| Rust       | 2                   | 2.3 MB      |\n| C++        | 4                   | 12.5 MB     |\n| Go         | 5                   | 4.3 MB      |\n| PHP        | 17                  | 19.8 MB     |\n| Python3    | 44                  | 17.8 MB     |\n| JavaScript | 74                  | 47.6 MB     |\n| C#         | 76                  | 40.2 MB     |\n\n![v5.png](https://assets.leetcode.com/users/images/3380a5d6-c26f-48b5-9cd2-c69a1bfc44aa_1698885598.7798116.png)\n\n\n# What We Learned\nThis problem teaches us the importance of optimizing our approach to avoid recalculating values for overlapping subtrees. By using a post-order traversal, we can calculate the sum and count for each subtree in a single pass, significantly improving the time complexity from $O(n^2)$ to $O(n)$. It also emphasizes the utility of using a nonlocal variable to keep track of the result during recursive traversal.
['Tree', 'PHP', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript', 'C#']