Modular Simple C++ | PostOrderTraversal
Intuition\n- Get the required details for a node using the same required details computed for its child nodes\n Describe your first thoughts on how to solve thi
# Intuition\n- Get the required details for a node using the same required details computed for its child nodes\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n- PostOrder Traversal\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nstruct Node {\n    int sizeOfSubtree;\n    vector<long long> maxPosNums;\n    vector<long long> maxNegNums;\n\n    Node() {\n        sizeOfSubtree = 0;\n        maxPosNums.resize(3, -1);\n        maxNegNums.resize(3, 1);\n    }\n\n    void recordPosNum(int num) {\n        if(num > maxPosNums[0])  {\n            maxPosNums[2] = maxPosNums[1];\n            maxPosNums[1] = maxPosNums[0];\n            maxPosNums[0] = num;\n        } else if(num > maxPosNums[1]) {\n            maxPosNums[2] = maxPosNums[1];\n            maxPosNums[1] = num; \n        } else if (num > maxPosNums[2])\n            maxPosNums[2] = num;\n    }\n\n    void recordNegNum(int num) {\n        if(num < maxNegNums[0])  {\n            maxNegNums[2] = maxNegNums[1];\n            maxNegNums[1] = maxNegNums[0];\n            maxNegNums[0] = num;\n        } else if(num < maxNegNums[1]) {\n            maxNegNums[2] = maxNegNums[1];\n            maxNegNums[1] = num; \n        } else if (num < maxNegNums[2])\n            maxNegNums[2] = num;\n    }\n\n    void recordNum(int num) {\n        if(num > 0)\n            recordPosNum(num);\n        else if(num < 0)\n            recordNegNum(num);\n    }\n\n    long long coinsAtThisNodeWhenAttrsAreValid() {\n        if(sizeOfSubtree < 3)\n            return 1;\n        \n        long long coins = 0;\n        if(maxPosNums[0] > 0 && maxPosNums[1] > 0 && maxPosNums[2] > 0)\n            coins = max(coins, maxPosNums[0] * maxPosNums[1] * maxPosNums[2]);\n        if(maxNegNums[0] < 0 && maxNegNums[1] < 0 && maxPosNums[0] > 0)\n            coins = max(coins, maxNegNums[0] * maxNegNums[1] * maxPosNums[0]);\n\n        return coins;\n    }\n};\n\nstruct Tree {\n    vector<vector<int>> adjList;\n    vector<Node> nodeDetails;\n    vector<bool> visitedNode;\n    vector<long long> coinsAtEachNode;\n    vector<int> costAtEachNode;\n\n    Tree(vector<vector<int>>& edges, vector<int>& cost) {\n        int n = edges.size() + 1;\n        adjList.resize(n);\n        nodeDetails.resize(n);\n        visitedNode.resize(n, false);\n        coinsAtEachNode.resize(n, -1);\n        costAtEachNode.resize(n, -1);\n\n        for(int i = 0; i < n; i++)\n            costAtEachNode[i] = cost[i];\n\n        for(vector<int>& edge: edges) {\n            adjList[edge[0]].push_back(edge[1]);\n            adjList[edge[1]].push_back(edge[0]);\n        }\n    }\n\n    void postOrderTraversal(int src) {\n        visitedNode[src] = true;\n        nodeDetails[src].sizeOfSubtree = 1;\n\n        nodeDetails[src].recordNum(costAtEachNode[src]);\n\n        for(int node: adjList[src])\n            if(!visitedNode[node]) {\n                postOrderTraversal(node);\n                nodeDetails[src].sizeOfSubtree += nodeDetails[node].sizeOfSubtree;\n                for(int x: nodeDetails[node].maxPosNums)\n                    nodeDetails[src].recordPosNum(x);\n                for(int x: nodeDetails[node].maxNegNums)\n                    nodeDetails[src].recordNegNum(x);\n            }\n        \n        coinsAtEachNode[src] = nodeDetails[src].coinsAtThisNodeWhenAttrsAreValid();\n    }\n};\n\nclass Solution {\npublic:\n    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {\n        Tree t(edges, cost);\n        t.postOrderTraversal(0);\n        return t.coinsAtEachNode;\n    }\n};\n```
['C++']