本文共 1113 字，大约阅读时间需要 3 分钟。

链接：

大意：

给定一个图节点node，要求深度复制整个图。给定图的数据结构如下：

class Node {    public int val;    public List
   
     neighbors;    public Node() {}    public Node(int _val,List
    
      _neighbors) {        val = _val;        neighbors = _neighbors;    }};
    
   

例子：

思路：

深度复制，使用dfs以及一个map保存图节点值到图节点的映射。

若当前图节点以存在（即map中存在相应键为图节点值），则返回该图节点的引用；否则新建图节点。

代码：

// 每个节点的值都是不一样的？ 每个节点的值都不一样  不然怎么访问给定值的邻居？class Solution {    public Node cloneGraph(Node node) {        Node n = new Node(node.val, new ArrayList<>());        Map
   
     map = new HashMap<>();        map.put(node.val, n);        dfs(node, n, map);        return n;    }    // 使用递归dfs构造cloneGraph    public void dfs(Node nodeOld, Node nodeNew, Map
    
      map) {        for (Node node : nodeOld.neighbors) {            if (!map.containsKey(node.val)) {                Node n = new Node(node.val, new ArrayList<>());                map.put(node.val, n);                nodeNew.neighbors.add(n);                dfs(node, map.get(node.val), map);            } else {                nodeNew.neighbors.add(map.get(node.val));            }        }    }}
    
   

结果：

结论：

算法+数据结构=程序 

转载地址：http://jxesi.baihongyu.com/