leetcode133. 克隆图

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int）和其邻居的列表（list[Node]）。

示例：

输入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释：
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

提示：

    节点数介于 1 到 100 之间。
    无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
    由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
    必须将给定节点的拷贝作为对克隆图的引用返回。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/clone-graph
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答：

1bfs:层序遍历

在图的遍历中分为层序遍历和深度遍历，和树的遍历基本相同。使用一个hashmap保存所有遇到的节点，借助一个队列linkedlist来实现层序遍历。

 1 /*

 2 // Definition for a Node.

 3 class Node {

 4     public int val;

 5     public List<Node> neighbors;

 6

 7     public Node() {}

 8

 9     public Node(int _val,List<Node> _neighbors) {

10         val = _val;

11         neighbors = _neighbors;

12     }

13 };

14 */

15 class Solution {

16     public Node cloneGraph(Node node) {

17         if(node==null)

18             return null;

19         HashMap<Node,Node> map=new HashMap<>();

20         LinkedList<Node> list=new LinkedList<>();

21         Node clone=new Node(node.val,new ArrayList<Node>());

22         map.put(node,clone);

23         list.add(node);

24         while(!list.isEmpty())

25         {

26             Node temp=list.remove();

27             for(Node n:temp.neighbors)

28             {

29                 if(!map.containsKey(n))

30                 {

31                     Node next=new Node(n.val,new ArrayList<Node>());

32                     map.put(n,next);

33                     list.add(n);

34                 }

35                  map.get(temp).neighbors.add(map.get(n));

36             }

37

38         }

39         return clone;

40     }

41 }

解法2：dfs深度遍历

对于深度遍历来说，依旧需要一个map保存已经创建过的node节点。每一层需要先判断map中是否已经有这个node，有的话就可以直接返回这个node的clone节点，不然需要创建clone节点返回。这道题就变成了递归，那么递归的三要素就需要好好考虑一下，这里的结束条件应该就是每个节点的neighbors列表遍历完全以后，所以当完成遍历neighbors就返回，返回值是什么呢？因为在遍历的时候还要往复制的node节点里面添加node引用，所以返回值就是复制的node节点，比如说在遍历1的neighbors时遇到2，进入2，那么我们需要返回2的复制节点，这样在1这个节点才会有2的复制，才可以往1的复制节点里面添加2的复制节点。

 1 /*

 2 // Definition for a Node.

 3 class Node {

 4     public int val;

 5     public List<Node> neighbors;

 6

 7     public Node() {}

 8

 9     public Node(int _val,List<Node> _neighbors) {

10         val = _val;

11         neighbors = _neighbors;

12     }

13 };

14 */

15 class Solution {

16     HashMap<Node,Node> map=new HashMap<>();

17     public Node cloneGraph(Node node) {

18         return dfs(node);

19     }

20     public Node dfs(Node node)

21     {

22         if(map.containsKey(node))

23             return map.get(node) ;

24         Node clone=new Node(node.val,new ArrayList<>());

25         map.put(node,clone);

26         for(Node n:node.neighbors)

27         {

28             Node temp=dfs(n);

29             clone.neighbors.add(temp);

30         }

31         return clone;

32     }

33 }

巴特西

leetcode133. 克隆图

最新文章

热门文章