类似Copy List With Random Pointer的问题，难点在于遍历图比遍历List更加复杂，基本思路还是一样的，
维护一个map，每一个原来的node对应新的node，第一个遍历的时候创建拷贝节点，之后在根据已有的map来build neighbors的list。 这里遍历图的时候我们采用BFS，注意BFS每次check邻接节点的时候要看是不是访问过并且加入visited set，而不是在queue中remove节点的时候加入visited set，第二种方法会导致queue中有重复的节点。值得注意的是。BFS中queue上的节点都是没有访问过的，且是没有重复的。要对节点做什么操作的话，在enqueue和dequeue的时候都可以，但是check访问过和更新visited set一定要在enqueue的时候。
代码如下：
No comments:
Post a Comment