[Leetcode] Minimum Height Trees

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]

Analysis:

The first thought is permuting the whole graph and depth first traversal them. But exceeding the time limit.

The second solution is from other guys (http://bookshadow.com/weblog/2015/11/26/leetcode-minimum-height-trees/), very elegant.

Its thought is to eliminate the leaves and remove the edge connected to leaves and add the newly leaves to a list. Finally the remaining node is the roots we want which are less or equal to two.

Solution 1

Time Complexity:

O(n^2)

class VertexNode {  
public:  
     VertexNode(int num) : label(num) {};  
     int label;  
     vector<int> edges;  
};  
class Solution {  
public:  
     void buildAdjcentList(vector<pair<int, int>>& edges, unordered_map<int, VertexNode*> & adjList)  
     {  
          for (pair<int, int> p : edges)  
          {  
               VertexNode * newnode1, *newnode2;  
               if (adjList.find(p.first) == adjList.end())  
               {  
                    newnode1 = new VertexNode(p.first);  
                    adjList[p.first] = newnode1;  
               }  
               else  
               {  
                    newnode1 = adjList[p.first];  
               }  
               if (adjList.find(p.second) == adjList.end())  
               {  
                    newnode2 = new VertexNode(p.second);  
                    adjList[p.second] = newnode2;  
               }  
               else  
               {  
                    newnode2 = adjList[p.second];  
               }  
               newnode1->edges.push_back(newnode2->label);  
               newnode2->edges.push_back(newnode1->label);  
          }  
     }  
     void DFSMHT(unordered_map<int, VertexNode*> & adjList, int curlabel, int prevlabel, int depth, int & minDepth)  
     {  
          VertexNode * curNode = adjList[curlabel];  
          if (!curNode) return;  
          if (curNode->edges.size() == 1 && curNode->edges[0] == prevlabel)  
          {  
               if (minDepth > depth)  
               {  
                    minDepth = depth;  
               }  
               return;  
          }  
          for (int i : curNode->edges)  
          {  
            if (i == prevlabel) continue;  
               DFSMHT(adjList, i, curNode->label, depth+1, minDepth);  
          }  
     }  
  vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {  
       unordered_map<int, VertexNode*> adjList;  
       buildAdjcentList(edges, adjList);  
       int minDepth = INT_MAX;  
       int curdepth = INT_MAX;  
       vector<int> retList;  
       for (pair<int, VertexNode*> it : adjList)  
       {  
            DFSMHT(adjList, it.second->label, -1, 1, curdepth);  
            if (curdepth <= minDepth)  
            {  
                 if (curdepth < minDepth)  
                      retList.clear();  
                 retList.push_back(it.second->label);  
                 minDepth = curdepth;  
            }  
            curdepth = INT_MAX;  
       }  
       return retList;  
  }  
};  

Solution 2

Time Complexity:

O(n)

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        children = collections.defaultdict(set)
        for x, y in edges:
        	children[x].add(y)
        	children[y].add(x)

        vertices = set(children.keys())

        while len(vertices) > 2:
        	leaves = [x for x in children if len(children[x]) == 1]
        	for x in leaves:
        		for y in children[x]:
        			children[y].remove(x)
        		del children[x]
        		vertices.remove(x)

        return list(vertices) if n != 1 else [0]

赏

谢谢你请我吃糖果