Python solution with detailed explanation


  • 0
    G

    Solution

    Minimum Height Trees https://leetcode.com/problems/minimum-height-trees/

    • The discuss posts are super helpful.
    • Brute force would be to try every node and find its height. This is N^2 solution.
    • Minimum height tree is rooted at the mid point of the longest path in the tree.
    • Here is one insight for this problem: the root of MHT is the middle point of the longest path in the tree; hence there are at most two MHT roots.
    • How to find them? We can BFS from the bottom (leaves) to the top until the last level with <=2 nodes. To build the current level from the previous level, we can monitor the degree of each node. If the node has degree of one, it will be added to the current level. Since it only check the edges once, the complexity is O(n).
    • Remember a tree has n nodes and n-1 edges.
    • https://discuss.leetcode.com/topic/30572/share-some-thoughts
    class Solution(object):
        def findMinHeightTrees(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: List[int]
            """
            degree = {k:0 for k in range(n)}
            graph = {k:set([]) for k in range(n)}
            for edge in edges:
                u,v = edge[0], edge[1]
                degree[u], degree[v] = degree[u]+1, degree[v]+1
                graph[u].add(v)
                graph[v].add(u)
            leaves = [k for k,v in degree.items() if v == 1]
            while leaves and len(graph) > 2:
                for leaf in leaves:
                    v = graph[leaf].pop()
                    del graph[leaf]
                    del degree[leaf]
                    degree[v] -= 1
                    graph[v].remove(leaf)
                leaves = [k for k,v in degree.items() if v == 1]
            return list(graph.keys())
    

    How will you find the longest path in a tree?


Log in to reply
 

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