Python | DFS | Easy Understand Interview Thought Process in 30 mins
DFS + Greedy\nThie is an undirected tree with n - 1 edges, meaning there is no cycle (it won\'t be called tree if there is cycle. The number of coins we place f
### DFS + Greedy\nThie is an undirected tree with `n - 1` edges, meaning there is no cycle (it won\'t be called tree if there is cycle. The number of coins we place for each node depends on the size of subtree rooted at each node `i` so defintely we need to travesal on the tree to count size for each subtree using post-order.\nOnce we get to know the size of subtree and costs for all of nodes within subtree, how can we efficiently calculate the maximum product of 3 distinct nodes?\nThen this problem is converted to be given a list of integers `nums`, how can we findout the maixmum product with 3 integers?\nLet\'s simplify the problem first. what if all of `nums` are positive? then it is easy to calculate the product with 3 largest nubmers among `nums`. \nThen what if adding negative numbers? it is possible for us to get postive prodcut with 2 negative numbers, and in order to get maximum postive prodcut we need 2 smallest numbers to time the largest number. \nIt looks good, but do we need to analyze each edge case separately? No, we can just calculate the potential maximum products regardless of postive or negative, and return the bigger one.\nSo it gives us the hint that we can get the maximum product by maintaining up to 5 numbers, 3 largest numbers and 2 smallest numbers.\nThen the algorithm looks like\n1. construct the tree with edges\n2.  run post-order traversal on the tree to count the size of subtree, and maintain 3 largest cost and smallest cost in the subtree\n3.  calculate the coin\n4.  return the coin array\n\n```python\ndef placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:\n\tn = len(cost)\n\tcoins = [0] * n \n\ttree = defaultdict(list)\n\tfor a, b in edges:\n\t\ttree[a].append(b)\n\t\ttree[b].append(a)\n\t\n\tdef get_coin(costs):\n\t\tif len(costs) < 3:\n\t\t\treturn 1\n\t\treturn max(\n\t\t\t0,\n\t\t\tcosts[-1] * costs[-2] * costs[-3],\n\t\t\tcosts[-1] * costs[0] * costs[1]\n\t\t)\n\n\tdef dfs(node, parent):\n\t\tsize = 1\n\t\tcosts = [cost[node]]\n\t\tfor child in tree[node]:\n\t\t\tif child != parent:\n\t\t\t\ts, c = dfs(child, node)\n\t\t\t\tsize += s\n\t\t\t\ttmp = sorted(costs + c)\n\t\t\t\tcosts = tmp[:2] + tmp[-3:] if len(tmp) > 5 else tmp \n\t\t\tcoins[node] = get_coin(costs)         \n\t\treturn size, costs\n                    \n\tdfs(0, -1)\n\treturn coins\n```\n\n*Time Comlexity* = **O(N)**\n*Space Complexity* = **O(N)**
[]