[C++] Depth-First Search with Sum and Count
Intuition\n Describe your first thoughts on how to solve this problem. \n- Use Depth-First Search\n- Pass the information (sum and count) of each child node to 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Use Depth-First Search\n- Pass the information (sum and count) of each child node to its parent node\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- For each node, get the information for children (DFS)\n- Calculate the sum and count of the current node\n- Update the result if matched\n\n# Complexity\n- Time complexity: $$O(n)$$, where `n` is the number of nodes in the binary tree\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(h)$$, where `h` is the height of the binary tree\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    // time/space: O(n)/O(h)\n    int averageOfSubtree(TreeNode* root) {\n        int result = 0;\n        helper(root, result);\n        return result;\n    }\nprivate:\n    pair<int, int> helper(TreeNode* node, int& result) {\n        // terminate\n        if (node == NULL) return {0, 0};\n\n        // recursive\n        auto [sum_left, count_left] = helper(node->left, result);\n        auto [sum_right, count_right] = helper(node->right, result);\n\n        // calculate the sum and count of the current node\n        int sum = node->val + sum_left + sum_right;\n        int count = 1 + count_left + count_right;\n\n        // update the result if matched\n        if (node->val == (sum / count)) result++;\n\n        return {sum, count};\n    }\n};\n```
['Tree', 'Depth-First Search', 'Recursion', 'Binary Tree', 'C++']