克隆图

LeetCode-133

使用一个map来存储已经遍历的结点，这个存起来的结点必须是新new的才符合题意

/*

// 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 {

    boolean[] flag;

    HashMap<Integer,Node>hashmap=new HashMap<>();

    public Node dfs(Node node){

        Node nows=new Node();

        nows.val=node.val;

        hashmap.put(node.val,nows);

        List<Node> list=node.neighbors;

        ArrayList<Node> newlist=new ArrayList<>();

        for(Node temp:list){

            Node now;

            if(!flag[temp.val]){

                flag[temp.val]=true;

                now=dfs(temp);

            }else {

                now=hashmap.get(temp.val);

            }

            newlist.add(now);

        }

        nows.neighbors=newlist;

        return nows;

    }

    public Node cloneGraph(Node node) {

        flag=new boolean[110];

        Arrays.fill(flag,false);

        if(node==null)

            return null;

        flag[node.val]=true;

        return dfs(node);

    }

}

巴特西

LeetCode-133克隆图（图的遍历+深拷贝概念）

克隆图

LeetCode-133

最新文章

热门文章