Another solution search from the outer most layer

  • 0
     from collections import defaultdict
        class Solution(object):
            def findMinHeightTrees(self, n, edges):
                :type n: int
                :type edges: List[List[int]]
                :rtype: List[int]
                if n == 1:
                    return [0]
                adjancy = defaultdict(set)
                for v in edges:
                degree_one = [k for k, v in adjancy.items() if len(v) == 1]
                while len(adjancy) > 2:
                    candidate = set()
                    for k in degree_one:
                        for nb in adjancy[k]:
                            if len(adjancy[nb]) == 1:
                        del adjancy[k]
                    degree_one = candidate
                return list(adjancy.keys())

    I feel the twice BFS/DFS method is the best. But here is an alternative. It performs layered search from the degree-1 nodes. Two tricks are:

    • The solution can only contain 0, 1, or 2 nodes;
    • The degree-1 nodes in the next round can only come from the ones
      whose degrees are reduced in the current round.

  • 0

    Just noticed that this solution is the same as the Java solution posted before. So just take it as a py solution for your reference

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.