310.Minimum Height Trees
Tags: [tree], [graph], [tree_height], [dp], [top_bottom_dp], [trick]
Link: https://leetcode.com/problems/minimum-height-trees/#/description
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.
Format
The graph containsnnodes which are labeled from0ton - 1. You will be given the numbernand a list of undirectededges(each edge is a pair of labels).
You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges.
Example 1:
Givenn = 4,edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
return[1]
Example 2:
Givenn = 6,edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return[3, 4]
Hint:
- How many MHTs can a graph have at most?
Note:
(1) According to thedefinition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected byexactlyone path. In other words, any connected graph without simple cycles is a tree.”
(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Solution: DP, Top To Bottom DP
class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
if not n:
return []
if not edges:
return [0]
# store the graph in adjacency list.
graph = {}
for edge in edges:
v1 = edge[0]
v2 = edge[1]
if v1 not in graph:
graph[v1] = set([v2])
else:
graph[v1].add(v2)
if v2 not in graph:
graph[v2] = set([v1])
else:
graph[v2].add(v1)
# try treat each vertex as the tree's root, and calculate its corresponding height.
tree_heights = []
memo = {}
for v in graph:
visited = set([v])
tree_heights.append((self.get_height(v, graph, visited, memo), v))
tree_heights.sort()
# collect the roots of trees who have min heights.
result = [tree_heights[0][1]]
for i in xrange(1, len(tree_heights)):
if tree_heights[i][0] == tree_heights[0][0]:
result.append(tree_heights[i][1])
return result
def get_height(self, root, graph, visited, memo):
root_has_child = False
max_height_of_subtree = 0
for child in graph[root]:
if child in visited:
continue
root_has_child = True
visited.add(child)
edge = '{}->{}'.format(root, child)
subtree_height = None
if edge in memo:
subtree_height = memo[edge]
else:
subtree_height = self.get_height(child, graph, visited, memo)
memo[edge] = subtree_height
max_height_of_subtree = max(max_height_of_subtree, subtree_height)
if not root_has_child:
return 0
return max_height_of_subtree + 1
Revelation:
- The height of the tree is the number of edges along the longest path from root to leaf. So when we calculate the height of the tree, if the root has no child the height should be 0, and if the root has child the height = 1 + max(sub trees' heights).
- Here we need to use 'visited' to mark which node has been visited, because the graph is undirected, so we need let the program not go back to the visited node.
- Here the memo's key is not the root, because when different vertex is the root, the height of each subtree can be different, like followings:
- When '3' is the root, the height of subtree (root = '1') = 1, but when '1' is root, the height of the tree(root = '1') = 2. So we cannot use root as the key of the memo. But we can use the edge (v1 -> v2) as the key of the memo. Because edge (v1 -> v2) contains the direction info, which is unique.
- The reason we can use DP because there exists overlapping computation. For example, when '3' is the root, we need calculate the height of the subtree (root = '1') ('1'->'0' and '1'->'4'), and when '2' is root, we also need to calculate the height of the subtree(root = '1') ('1'->'0' and '1'->'4'), and also when '1' is the root, we still need to calculate the height of subtree(root = '1') ('1' ->'0' and '1'->'4'). So we can just calculate once the height of subtree(root = '1')('1'->'0' and '1'->'4') and record them in the memo['1'->'0'] and memo['1'->'4'], be ready to be used later.
- Do not forget the corner case: there is only one vertex('0'), and no edges, under this scenario we should return [0].
Note:
- Time complexity = O(len(edges) + 2 * len(edges)) = O(len(edges)), len(edges) is the number of edges.
Time Limited Exceeded:
class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
if not n:
return []
if not edges:
return [0]
# store the graph in adjacency list.
graph = {}
for edge in edges:
v1 = edge[0]
v2 = edge[1]
if v1 not in graph:
graph[v1] = set([v2])
else:
graph[v1].add(v2)
if v2 not in graph:
graph[v2] = set([v1])
else:
graph[v2].add(v1)
# try treat each vertex as the tree's root, and calculate its corresponding height.
tree_heights = []
for v in graph:
visited = set([v])
tree_heights.append((self.get_height(v, graph, visited), v))
tree_heights.sort()
# collect the roots of trees who have min heights.
result = [tree_heights[0][1]]
for i in xrange(1, len(tree_heights)):
if tree_heights[i][0] == tree_heights[0][0]:
result.append(tree_heights[i][1])
return result
def get_height(self, root, graph, visited):
root_has_child = False
max_height_of_subtree = 0
for child in graph[root]:
if child in visited:
continue
root_has_child = True
visited.add(child)
max_height_of_subtree = max(max_height_of_subtree, self.get_height(child, graph, visited))
if not root_has_child:
return 0
return max_height_of_subtree + 1
Note:
- Time complexity = O(len(edges) + n^2), len(edges) is the number of edges, n is the number of vertices.