Leetcode - 133. 克隆图

/*
// 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 Node[] clonedNodes;

    // 假设题目给定的图是1 - 2 - 3 - 4 - 1
    // 那么我们可以先新创建1, 2, 3, 4这四个节点，把它们放入clonedNodes[1:4]中
    //  - 由于原1节点有2和4两个邻居节点，因此clonedNodes[1]的neighbors集合也放入clonedNodes[2]和clonedNodes[4]节点
    //  - 由于原2节点有1和3两个邻居节点，因此clonedNodes[2]的neighbors集合也放入clonedNodes[1]和clonedNodes[3]节点
    //  - ...
    // 当所有节点都克隆完成，整个图就克隆完成了
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        
        // 初始化clonedNodes数组
        // 由于节点个数不超过100，且val值在1和100之间，因此数组大小设置为101即可
        clonedNodes = new Node[101];
        
        // 以node为模板克隆一个新的节点
        // 这一步会递归地克隆node的邻居节点
        return cloneNode(node);
    }

    // 克隆node节点（及其邻居节点）
    private Node cloneNode(Node node) {
        
        // 拿到该节点的克隆节点（该节点可能未被初始化）
        Node clonedNode = getNthClonedNode(node.val);
        
        // 如果该克隆节点的val值为0，说明它的邻居列表还没有初始化
        // 此时先将其val值更新为node.val，然后再更新其neighbors集合
        if (clonedNode.val == 0) {
            clonedNode.val = node.val;
            for (Node neighbor : node.neighbors) {
            
                // 克隆邻居节点，并将克隆后的节点添加到clonedNode的邻居列表中
                clonedNode.neighbors.add(cloneNode(neighbor));
            }   
        }
        
        return clonedNode;
    }

    // 获取第n个克隆节点；注意返回的节点可能仅仅是刚实例化，而未初始化
    private Node getNthClonedNode(int n){
        
        // 如果数组中还没有对应的副本，则先创建一个空节点
        // 新创建的节点的val值为0，因此我们可以通过节点的val值来判断它的邻居节点是否已经被设置
        if (clonedNodes[n] == null) {
            clonedNodes[n] = new Node();
        }
        
        // 返回数组中第n个元素
        return clonedNodes[n];
    }
}