Easy to understand C++ Solution | Post Order | DFS | O(n)
Intuition\n Describe your first thoughts on how to solve this problem. \nWe are asked to count the nodes with highest score. \nScore of a node is nothing but pr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe are asked to count the nodes with highest score. \n**Score of a node** is nothing but product of number of nodes in the remaining forests after removing that node from the tree. \n\n**Important Observation**:\nWe can categorize the nodes into three cases\n1. **Root Node** - A score of a root node is just the product of number of nodes in left sub tree and number of nodes in right sub tree i.e `leftSubTreeNodes * rightSubTreeNodes`, Since a root node doesn\'t have a parents, we will have at most two forests when we remove the node \n2. **Leaf Node** - Since a leaf node doesn\'t have any children, on deleting a leaf node we get one forest. So, the score of the leaf node is `numberOfNodesInATree` - 1\n3. **Middle Node** - A Middle node can have both children and a parent. So, when we delete a middle node, we get 3 forests. Score of a middle node is `leftSubTreeNodes * rightSubTreeNodes *otherNodes`.\n\nOn careful observation cases 2 and 3 can be simplified and combined into one case.\n`leftSubTreeNodes * rightSubTreeNodes * (numberOfTreeNodes - (lefSubTreeNodes + rightSubtreeNodes +1))`, *because other nodes can be calculated as total no of nodes - no of child nodes + 1(including the current node). Also, for leafnodes, we don\'t include the child nodes while computing the score.*\n\n*For Root node however, since we don\'t have a parent, the other nodes will be 0, so we don\'t include that while computing the score for that node.*\n\nSince, we want to know the count in the left subtrees and right subtrees before computing the score every node, we use the postOrder traversal.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Create an adjacency list for the tree from the parents array.\n2. Do a post order traversal. \n3. In the post order traversal, while traversing the node, compute the score according to the above algorithm, update the maximum score if it\'s greater than the previous max score and the set the maxScore Count to 1.\n4. If the score equal to maxScore, update the maxScore Frequency\n\n\n# Complexity\n- Time complexity: `O(n)`\nWe are traversing all the nodes in the Tree exactly once. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(n)` - to store the adjaceny list\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> graph;\n    long long maxScore = 0;\n    int root = -1;\n    int maxScoreFrequency = 0;\n\n    int dfs(int node) {\n        int count = 0;\n        long long score = 1;\n        for(auto adj: graph[node]){\n            auto child = dfs(adj);\n            count += child;\n            score *= child;\n        }\n        if(node != root) score *= (graph.size() -(count + 1));\n        if(maxScore < score) {\n            maxScore = score;\n            maxScoreFrequency = 1;\n        } else if(maxScore == score) {\n            maxScoreFrequency++;\n        }\n        return count +1;\n    }\n\n    int countHighestScoreNodes(vector<int>& parents) {\n        graph.resize(parents.size());\n        for(int i = 0 ; i < parents.size(); i++) {\n            if(parents[i] != -1) {\n                graph[parents[i]].push_back(i);\n            }else {\n                root = i;\n            }\n        }\n        dfs(root);\n        return maxScoreFrequency;\n    }\n};\n```
['C++']