Leetcode 133. Clone Graph

方法1: dfs。这是一道graph题，我第一感觉是要用recursion来做的。我离正确答案离的很近，最近好久没做题，有点生疏，如果是之前手感，做出来应该没问题。我没做出来主要是我使用了set而不是map，在怎样避免操作重复node上面我理解的不对。还是那句话，多联系吧，这题不难，应该拿下的。复杂度复盘看。

/*
// 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 {
    private Map<Node, Node> visited = new HashMap<>(); 
    public Node cloneGraph(Node node) {
        if(node == null){
            return node;
        }
        if(visited.containsKey(node)){
            return visited.get(node);
        }
        Node root = new Node(node.val, new ArrayList<>());
        visited.put(node, root);
        for(Node n : node.neighbors){
            root.neighbors.add(cloneGraph(n));
        }
        return root;
    }
}

方法2: bfs，方法1的变种，用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;
        Map<Node, Node> visited = new HashMap<>(); 
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        visited.put(node, new Node(node.val, new ArrayList<>()));
        while(!queue.isEmpty()){
            Node curr = queue.poll();
            for(Node n : curr.neighbors){
                if(!visited.containsKey(n)){
                    visited.put(n, new Node(n.val, new ArrayList<>()));
                    queue.offer(n);
                }  
                visited.get(curr).neighbors.add(visited.get(n));
            }
        }
        return visited.get(node);
    }
}

总结：

• 无