310. Minimum Height Trees
- Total Accepted: 20625
- Total Submissions: 74043
- Difficulty: Medium
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 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]
Note:
(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one 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.
Code
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 == 0: return []
if n == 1: return [0]
res = []
adj = defaultdict(set)
for e in edges:
adj[e[0]].add(e[1])
adj[e[1]].add(e[0])
leaves = self.build_leaves_from_adj(adj)
while n > 2:
n = n - len(leaves)
for l in leaves:
adj[adj[l].pop()].remove(l)
adj.pop(l)
leaves = self.build_leaves_from_adj(adj)
return leaves
def build_leaves_from_adj(self, adj):
return [k for k, v in adj.iteritems() if len(v) <= 1]
Idea
Imagine you are doing BFS from the current leaves. In every iteration, you remove all edges connected with leaves and leaf nodes themselves. Then, you re-identify new leaves. You repeatedly do this until at most two nodes left. The remaining nodes are the rooted nodes for MHT.
Reference:
https://discuss.leetcode.com/topic/30572/share-some-thoughts/2
Code
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 == 0: return []
if n == 1: return [0]
res = []
adj = defaultdict(set)
for e in edges:
adj[e[0]].add(e[1])
adj[e[1]].add(e[0])
max_path = self.maxpath(adj, edges[0][0], None)
max_path = self.maxpath(adj, max_path[-1], None)
l = len(max_path)
if l % 2 == 0:
return max_path[l/2-1:l/2+1]
else:
return max_path[l/2:l/2+1]
def maxpath(self, adj, cur_node, prev_node):
max_path = [cur_node]
for n in adj[cur_node]:
# check whether the next visiting node is not visited before.
# use the property that tree has no cycle. just need to check with last visited node.
if n != prev_node:
new_max_path = [cur_node] + self.maxpath(adj, n, cur_node)
if len(max_path) < len(new_max_path):
max_path = new_max_path
return max_path
Idea (From https://discuss.leetcode.com/topic/30956/two-o-n-solutions)
Longest Path
It is easy to see that the root of an MHT has to be the middle point (or two middle points) of the longest path of the tree.
Though multiple longest paths can appear in an unrooted tree, they must share the same middle point(s).
Computing the longest path of a unrooted tree can be done, in O(n) time, by tree dp, or simply 2 tree traversals (dfs or bfs).
The following is some thought of the latter.
Randomly select a node x as the root, do a dfs/bfs to find the node y that has the longest distance from x.
Then y must be one of the endpoints on some longest path.
Let y the new root, and do another dfs/bfs. Find the node z that has the longest distance from y.
Now, the path from y to z is the longest one, and thus its middle point(s) is the answer.