Another solution search from the outer most layer


  • 0
    S
     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:
                    adjancy[v[0]].add(v[1])
                    adjancy[v[1]].add(v[0])
                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]:
                            adjancy[nb].remove(k)
                            if len(adjancy[nb]) == 1:
                                candidate.add(nb)
                        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
    S

    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.