From 九章算法:
采用BFS。
set up Graph真的考验功力
这里的map用来判断一个Node是否被visited 过。
Nodes这个arrayList充当 queue的作用。 因为BFS需要一个优先队列。这里的BFS其实算是一个模板,该背就背。
注意,这里的queue里的node不能pop出来!因为pop出来的话到时候没办法搞。
最后这部map.get(node)的原因是Hashmap里存的是<original Node, clone Node>的配对。 所以map.get(node)就是返回root clone node、