133. Clone Graph - Medium

前往題目

寫過了，搬運一下~

想法

• 這題依舊沒發現可以用BFS，但是有想過484可以
• DFS也可以!反正就是疊代樹
• 基本上就是使用hashmap來儲存對應關係，用來判斷clone了沒
• 然後DFS或BFS所有節點

思路

1. A hashmap for old node to new node
2. dfs
3. if the node already in the map, return it
4. Otherwise, copy it and map it
5. gone through each node’s neighbours
6. Return the node (Watch out null)

Code

// origin to clone mapping
HashMap<Node, Node> oldToNew = new HashMap<>();

public Node cloneGraph(Node node) {
    /*
    Idea:
        1. A hashmap for old node to new node
        2. dfs
        3. if the node already in the map, return it
        4. Otherwise, copy it and map it
        5. gone through each node's neighbours
        6. Return the node (Watch out null)
    */

    // Base case
    if (node == null) return null;

    // Cloned already
    if (oldToNew.containsKey(node)) return oldToNew.get(node);

    // New node for clone
    Node newNode = new Node(node.val, new ArrayList<Node>());

    // Copy it
    oldToNew.put(node, newNode);

    // Iterate through the neighbors
    for (Node neighbors : node.neighbors) {
        newNode.neighbors.add(cloneGraph(neighbors));
    }

    return newNode;
}

2024/01/07

• 沒想出來，以為要用Set，要用應該也是可以但會要更多的資料結構輔助，太冗餘了
• Recursion依舊沒那麼直覺…只能多做題目了吧