directed graph BFS 里靠 indegree = 0 判断加入队列；
undirected graph BFS 里靠 degree = 0 判断加入队列；
先说下自己一个 TLE 的初始尝试：根据所有 Edges 建 ArrayList[] 的 Graph，同时存每个点的 Adjacency lists，考虑到是无向图，对于每一个 edge 我们需要在两个 list 中更新才行。然后维护一个 HashMap<> 存着每一个 height 对应的 List<>，然后循环扫描每一个点作为起点进行 BFS，找到最小 height 之后 map.get(height) 就可以了。
然而这种做法的时间复杂度是 O(V * (E + V)) ，每个点都要扫整个 graph ，太高了。
转换一下思路，我们做的事情其实非常近似于
Find Leaves of Binary Tree , 对于一个形状和链表一样的图，我们知道最优解一定是中点；对于一个 inorder traversal array，我们知道 height balanced tree 也一定以中点为 root;
在这个 graph 里，我们要找的，其实也是一层一层剥开最外围 nodes 之后，最里面的点。
因此，即使是 undirected graph，degree 也是非常重要的信息，只不过对于 undirected graph 来讲:
degree = "in"-degree + "out"-degree 而已.
AC代码，速度击败了 95.98 % ~
O(E + V)
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
int[] degrees = new int[n];
ArrayList[] graph = new ArrayList[n];
for(int i = 0; i < n; i++){
graph[i] = new ArrayList<>();
}
for(int[] edge : edges){
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
degrees[edge[0]]++;
degrees[edge[1]]++;
}
Queue<Integer> queue = new LinkedList<Integer>();
for(int i = 0; i < n; i++){
if(degrees[i] <= 1) queue.offer(i);
}
List<Integer> list = new ArrayList<>();
while(!queue.isEmpty()){
int size = queue.size();
list = new ArrayList<>();
for(int i = 0; i < size; i++){
int node = queue.poll();
list.add(node);
for(int j = 0; j < graph[node].size(); j++){
int next = (int)graph[node].get(j);
degrees[next] --;
if(degrees[next] == 1) queue.offer(next);
}
}
}
return list;
}
}
这题我之前写 union-find 的时候做过了，确实是更快更高效的写法。不过这题也完全可以用 Graph 上的常规 BFS / DFS 求解.
这题用 BFS 解需要解决这么几个问题：
如何正确 detect cycle?
常规 indegree 的话，如果有 cycle 会有一些点因为 indegree 无法进一步缩小的问题永远不被访问，可以记录 visited count;
另一种方法是，用 int[] 表示每个点的状态，其中
如果在循环的任何时刻，我们试图访问一个状态为 “1” 的节点，都可以说明图中有环。
如何正确识别图中 connected components 的数量?
添加任意点，探索所有能到达的点，探索完毕数量 +1；
如此往复，直到已探索点的数量 = # of V in graph 为止。
BFS 做法，时间复杂度 O(E + V);
public class Solution {
public boolean validTree(int n, int[][] edges) {
int[] states = new int[n];
ArrayList[] graph = new ArrayList[n];
for(int i = 0; i < n; i++){
graph[i] = new ArrayList();
}
for(int[] edge : edges){
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
states[0] = 1;
int count = 0;
while(!queue.isEmpty()){
int node = queue.poll();
count ++;
for(int i = 0; i < graph[node].size(); i++){
int next = (int) graph[node].get(i);
if(states[next] == 1) return false ;
else if(states[next] == 0){
states[next] = 1;
queue.offer(next);
}
}
states[node] = 2;
}
return count == n;
}
}
一次 AC ~ 由于不用考虑环和拓扑顺序，BFS 的方式就很简单，记录下看过哪些点就可以了。
参考了下论坛讨论之后，不太同意大多数解法，因为假设所有点的 label 唯一不是很适合 generalize 这个算法。用 HashMap<> 实现 Node - Node mapping 比较靠谱。
下面的代码简化了一下，参考了九章的写法，先用一个 getNodes 函数返回所有的节点(因为函数就给了一个)，在返回的时候直接 new ArrayList<>(set) 调用 Collection constructor.
这样算法逻辑就分成两步：
过一遍所有节点，建新节点放到 HashMap 中；
再过一遍所有节点，这次更新每个对应节点的 neighbors.
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return node;
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
List<UndirectedGraphNode> nodeList = getNodes(node);
for(UndirectedGraphNode cur : nodeList){
map.put(cur, new UndirectedGraphNode(cur.label));
}
for(UndirectedGraphNode cur : nodeList){
UndirectedGraphNode copy = map.get(cur);
for(UndirectedGraphNode neighbor : cur.neighbors){
copy.neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
private List<UndirectedGraphNode> getNodes(UndirectedGraphNode node){
Set<UndirectedGraphNode> visited = new HashSet<>();
Queue<UndirectedGraphNode> queue = new LinkedList<>();
queue.offer(node);
visited.add(node);
while(!queue.isEmpty()){
UndirectedGraphNode cur = queue.poll();
for(UndirectedGraphNode next : cur.neighbors){
if(!visited.contains(next)){
visited.add(next);
queue.offer(next);
}
}
}
return new ArrayList<>(visited);
}
}
链表也是图啊，就是这么简单，轻松，愉快~~
这题还有一个比较妖孽的 follow-up，不让用 HashMap. 做法就是在每个节点后面插入新节点，最后再拆出来就行了，复杂度依然 O(n).
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode cur;
for(cur = head; cur != null; cur = cur.next){
map.put(cur, new RandomListNode(cur.label));
}
for(cur = head; cur != null; cur = cur.next){
RandomListNode copy = map.get(cur);
copy.random = map.get(cur.random);
copy.next = map.get(cur.next);
}
return map.get(head);
}
}