🌕🌕🌕 133. 克-图

难度: 🌕🌕🌕

问题描述

---

解法 1 - dfs

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    HashMap<Node, Node> map;
    public Node cloneGraph(Node node) {
        // 思路：
        // 就是遍历 node 的所有节点，将所有节点的值复制成一个新节点，neighbors 同样复制成新的各个节点
        // 需要注意的，已经复制过的节点不需要再次复制，造成死循环
        // 深度优先
        map = new HashMap<>();
        mySol(node);
        return map.get(node);
    }

    private Node mySol(Node node) {
        // 递归终止条件
        if(node == null) {
            return null;
        }
        // node != null
        if(map.containsKey(node)) {
            return map.get(node); // 已经完成该节点的复制，直接返回复制的新节点
        }
        Node newNode = new Node(node.val); // 先复制原节点的值
        map.put(node, newNode); // 复制值后，直接返回，防止出现循环
        
        // 遍历邻接点，这些也需要完成对应的复制
        ArrayList<Node> list = new ArrayList<>();
        for(Node cur : node.neighbors) {
            if(map.containsKey(cur)) {
                list.add(map.get(cur));
            } else {
                // 完成邻接点的复制，递归
                list.add(mySol(cur));
            }
        }
        // 邻接点所有也已完成复制过程，即深拷贝，更新
        newNode.neighbors = list;
        return newNode; // 返回深拷贝的新节点
    }
}

---

输出 1

---

解法 2 - bfs

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        // 思路：
        // 广度优先 - 辅助 队列
        if(node == null) {
            return node;
        }
        HashMap<Node, Node> map = new HashMap<>();
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(node);
        while(!queue.isEmpty()) {
            int len = queue.size();
            for(int i = 0; i < len; i ++) {
                Node cur = queue.poll();
                Node cloneCur;
                if(map.containsKey(cur)) {
                    // map 中已经有 cur 的复制节点
                    cloneCur = map.get(cur);
                } else {
                    // 需要构造
                    cloneCur = new Node(cur.val);
                    map.put(cur, cloneCur);
                }
                // 完成值复制后，及时更新 map，不需要等到完成邻接表的复制，原因是 map 中存放的只是 node
                // 完成后面的邻接表的复制之后，可以之后更新，map 中找到的 node 还是之前的复制节点
                ArrayList<Node> list = new ArrayList<>();
                for(Node tmp : cur.neighbors) {
                    if(map.containsKey(tmp)) {
                        list.add(map.get(tmp));
                    } else {
                        Node cloneTmp = new Node(tmp.val);
                        map.put(tmp, cloneTmp); // 创建复制节点
                        queue.offer(tmp);
                        list.add(cloneTmp);
                    }
                }
                cloneCur.neighbors = list;
            }
        }
        return map.get(node);
    }
}

---

输出 2