Q310. Minimum Height Trees
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.
Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).
Return a list of all MHTs' root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Example 1:
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
Example 2:
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
Example 3:
Input: n = 1, edges = []
Output: [0]
Example 4:
Input: n = 2, edges = [[0,1]]
Output: [0,1]
Constraints:
1 <= n <= 2 * 104
edges.length == n - 1
0 <= ai, bi < n
ai != bi
All the pairs (ai, bi) are distinct.
The given input is guaranteed to be a tree and there will be no repeated edges.
For me, it is super hard to get the idea initially. And the implementation itself is also quite challenging for me. Because of this, I think it is good to write it down for future re-visit.
The height of the tree is the maximum depth among all leaves. So, if we want to minimize the height of the tree (to determine where to put the root), we want the depth of all leaves to be as even as possible. To make it even, the actual problem focuses on the longest path between two leaves. The root has to locate on this path otherwise, the height should be determined by one of the two leaves of this path anyway and we can always reduce the depth to these two leaves by moving the root to this path.
OK, then, the question is to identify the middle point(s) of the longest path. There could be one or two of them. The strategy to obtain the longest path is by constantly pruning the current leaves of the tree. The idea is that we shrink the tree in all directions equally and the middle part of the longest path will be the last chunk to be removed.
OK, the algorithm is:
- Initialize the list of current leaves.
- At each iteration, go through all leaves and pruning them. Update the list of current leaves.
- Prune until there are only one or two leaves.
The Python submission is:
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if len(edges) == 0:
return [ i for i in range(n) ]
# build adjacent graph
graph = [ [[], 0] for _ in range(n)]
for i, j in edges:
graph[i][0].append(j)
graph[i][1] += 1
graph[j][0].append(i)
graph[j][1] += 1
trash_bin = {}
leaves = deque()
leaved = {}
for i in range(n):
if graph[i][1] == 1:
leaves.append(i)
leaved[i] = 1
while len(trash_bin) < n - 2:
for i in range(len(leaves)):
leave = leaves.popleft()
trash_bin[leave] = 1
for nn in graph[leave][0]:
graph[nn][1] -= 1
# print(trash_bin)
if nn not in trash_bin and nn not in leaved and graph[nn][1] == 1:
leaves.append(nn)
leaved[nn] = 1
return leaves