LeetCode 310. Minimum Height Trees
Description
For an 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 :
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
Output: [1]
Example 2 :
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
Output: [3, 4]
Note:
- 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.”
- The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
描述
对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
注意：
该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。
你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。
示例 1:
输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
输出: [1]
示例 2:
输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
输出: [3, 4]
说明:
- 根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
- 树的高度是指根节点和叶子节点之间最长向下路径上边的数量。
思路
- 最小高度树的根节点是图中最长路径的中间节点.
- 我们用一个 List[set()] 的结构存储每个节点可以访问到的其他节点。一般情况下应该使用字典，以节点为键，能够遍历到的节点组成的哈希set为键，但由于题中的节点是从0开始的数字，我们可以用 List 来代替，索引就是键。
- 最长路径的中间节点最多会有两个：最长路径有奇数个节点，则中间节点有 1 个；最长路径有偶数个节点，则中间节点有 2 个。
- 基本思路是:找到所有的叶子节点，去掉所有叶子节点，找到新的所有叶子节点，去掉所有叶子节点 ... 直到剩下的节点个数小于等于2个。
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-02-17 13:46:09
# @Last Modified by: 何睿
# @Last Modified time: 2019-02-17 14:15:30
class Solution:
def findMinHeightTrees(self, n: 'int',edges: 'List[List[int]]') -> 'List[int]':
# 如果只有一个节点，直接返回当前节点
if n == 1: return [0]
# 路径：记录每个节点可以访问到的所有节点 type:list[set()]
# 更一般的情况是利用字典实现，利用节点作为键，节点能够走到的所有节点
# 组成的set作为值，但是题中得节点为从0开始的数值，因此可以用list代替字典
paths = [set() for _ in range(n)]
# 找到每个节点可以走到的下一个节点
for node1, node2 in edges:
paths[node1].add(node2)
paths[node2].add(node1)
# 找到所有的叶子节点
leaves = [node for node in range(n) if len(paths[node]) == 1]
# root用于记录剩下的节点
roots = n
while roots > 2:
# 更新剩下的节点个数
roots -= len(leaves)
# 新的叶子节点
newleaves = []
for node in leaves:
# 获取叶节点的父节点
parent = paths[node].pop()
# 从叶节点的父节点中删除当前节点
paths[parent].remove(node)
# 如果当前节点的父节点只能访问一个节点，则添加到新叶节点中
if len(paths[parent]) == 1: newleaves.append(parent)
leaves = newleaves
return leaves
