python, BFS, bottom-up, no recursion, w/ thinking process
This is my thinking process:\nLet\'s start with the easy parts. For leaf nodes, it is easy: each apple node costs 2 steps. \nAfter eliminate the real leaf nodes
This is my thinking process:\nLet\'s start with the easy parts. For leaf nodes, it is easy: each apple node costs 2 steps. \nAfter eliminate the real leaf nodes, nodes in the second lowest level become new leaves, and we can treat them the same except that:\n1) if it has an apple child, it needs to be traversed. We don\'t need to separate real apple nodes from nodes that needs to be travesed because of apple child, so to achieve this, we can simply mark the parent as apple each time we meet an apple node.\n2) For each apple node (\'real\' apple node or marked apple nodes because of apple child), we need 2 steps to reach them + steps needed for its apple decendants. \n\n\n```python\ndef minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        d_neighbors = collections.defaultdict(set)\n        for a,b in edges:\n            d_neighbors[a].add(b)\n            d_neighbors[b].add(a)\n        \n        steps = [0] * n\n        \n        leafs = set(node for node, lst_neighbor in d_neighbors.items() if len(lst_neighbor) == 1 )\n        leafs.discard(0)\n        \n        while leafs:\n            new_leafs = set()\n            for leaf in leafs:\n                parent = d_neighbors[leaf].pop()\n                if hasApple[leaf]:\n                    steps[parent] += 2 + steps[leaf]\n                    hasApple[parent] = True\n                d_neighbors[parent].discard(leaf)\n                if len( d_neighbors[parent] ) == 1:\n                    new_leafs.add( parent )\n            leafs = new_leafs\n            leafs.discard(0)\n            \n        return steps[0]\n```\n\nI think the BFS part of the code is pretty self-explanatary. If you have difficulty to understand, there are some problems with very similar BFS code as answer:\n\n310\xA0Minimum Height Trees\n127 Word Ladder\n
[]