Python 3 | Graph, DFS, Post-order Traversal, O(N) | Explanation
Explanation\n- Intuition: Maximum product of 3 branches, need to know how many nodes in each branch, use DFS to start with\n- Build graph\n- Find left, right, u
### Explanation\n- Intuition: Maximum product of 3 branches, need to know how many nodes in each branch, use `DFS` to start with\n- Build graph\n- Find left, right, up (number of nodes) for each node\n\t- left: use recursion\n\t- right: use recursion\n\t- up: `n - 1 - left - right`\n- Calculate score store in a dictinary\n- Return count of max key\n- Time: `O(n)`\n### Implementation     \n```\nclass Solution:\n    def countHighestScoreNodes(self, parents: List[int]) -> int:\n        graph = collections.defaultdict(list)\n        for node, parent in enumerate(parents):  # build graph\n            graph[parent].append(node)\n        n = len(parents)                         # total number of nodes\n        d = collections.Counter()\n        def count_nodes(node):                   # number of children node + self\n            p, s = 1, 0                          # p: product, s: sum\n            for child in graph[node]:            # for each child (only 2 at maximum)\n                res = count_nodes(child)         # get its nodes count\n                p *= res                         # take the product\n                s += res                         # take the sum\n            p *= max(1, n - 1 - s)               # times up-branch (number of nodes other than left, right children ans itself)\n            d[p] += 1                            # count the product\n            return s + 1                         # return number of children node + 1 (self)\n        count_nodes(0)                           # starting from root (0)\n        return d[max(d.keys())]                  # return max count\n```
['Depth-First Search', 'Graph', 'Python', 'Python3']