C++ postOrder, inOrder, preOrder transversal->0ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nQuite standard problem for binary trees.\nUsing postOrder, inOrder, preOrder transversa
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nQuite standard problem for binary trees.\nUsing postOrder, inOrder, preOrder transversal to solve the problem.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBe careful with the definition of average!\n```\nFor the node with value 5: The average of its subtree is \n(5 + 6) / 2 = 11 / 2 = 5.\n```\nUsing the similar idea from @Sergei, the optimized code does not use the pair<int, int>, insteadly uses an unsigned long long, using first 32-bit part for n the number of nodes in subtree , the second 32-bits part for sum of the node values in subtree.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$ + system stack for recursion\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 {\n    using int2=pair<int, int>;\npublic:\n    int count=0;\n    int2 preOrder(TreeNode* node){\n        if (node==NULL) return {0, 0};\n        int sum=node->val, i=1;\n        auto [sumL, iL]=preOrder(node->left);\n        auto [sumR, iR]=preOrder(node->right);\n        sum+=(sumL+sumR);\n        i+=(iL+iR);\n        if (sum/i==node->val) count++;\n    //    cout<<node->val<<" n="<<i<<" sum="<<sum<<endl;\n        return {sum, i};\n    }\n\n    int2 postOrder(TreeNode* node){\n        if (node==NULL) return {0, 0};\n        auto [sumL, iL]=postOrder(node->left);\n        auto [sumR, iR]=postOrder(node->right);\n        int sum=node->val, i=1;\n        sum+=(sumL+sumR);\n        i+=(iL+iR);\n        if (sum/i==node->val) count++;\n    //    cout<<node->val<<" n="<<i<<" sum="<<sum<<endl;\n        return {sum, i};\n    }\n\n    int2 inOrder(TreeNode* node){\n        if (node==NULL) return {0, 0};\n        auto [sumL, iL]=inOrder(node->left);\n        int sum=node->val, i=1;\n        auto [sumR, iR]=inOrder(node->right);\n        sum+=(sumL+sumR);\n        i+=(iL+iR);\n        if (sum/i==node->val) count++;\n    //    cout<<node->val<<" n="<<i<<" sum="<<sum<<endl;\n        return {sum, i};\n    }\n\n    int averageOfSubtree(TreeNode* root) {\n        inOrder(root);\n        return count;\n    }\n};\n```\n# Code runs 0ms & beats 100%\n```\n#pragma GCC optimize ("O3")\nclass Solution {\npublic:\n    signed count=0;\n    signed long long inOrder(TreeNode* node){\n        if (node==NULL) return 0;\n        signed long long sum_n_L=inOrder(node->left);\n        signed long long sum_n=node->val+(1L<<32);\n        signed long long sum_n_R=inOrder(node->right);\n        sum_n+=sum_n_L+sum_n_R;\n        if ((sum_n&0xffffffff)/(sum_n>>32 )==node->val) count++;\n    //    cout<<node->val<<" n="<<i<<" sum="<<sum<<endl;\n        return sum_n;\n    }\n\n    int averageOfSubtree(TreeNode* root) {\n        inOrder(root);\n        return count;\n    }\n};\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Recursion', 'Binary Tree', 'C++']