一.复杂链表的复制

二.克隆二叉树

三.克隆含随机指针的二叉树

四.克隆N叉树

五.克隆图

一.复杂链表的复制

复制链表的复制由于之前以及写过了，在这里直接给出博客的链接。

复杂链表的复制_一个山里的少年的博客-CSDN博客

二.克隆二叉树

375 · 克隆二叉树 - LintCode

题目描述：

解题思路：

本题和上面那题的思路一样使用Hash表建立克隆节点和原节点之间的对应关系。在这里我才能宽度优先遍历来解决。具体可以参考我写的代码和上一篇博客。

对应代码：

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: The root of binary tree
     * @return: root of new tree
     */
    TreeNode * cloneTree(TreeNode * root) {
        if(root==nullptr)//空树
        {
            return nullptr;
        }
        // write your code here
        queue<TreeNode*>q;
        unordered_map<TreeNode*,TreeNode*>Hash;//建立原节点和克隆节点之间的关系
         q.push(root);
       Hash[root]=new TreeNode(root->val);//建立关系
        while(!q.empty())
        {
            auto node=q.front();//从队列中拿出一个节点
            q.pop();
            if(node->left)//如果他的左树不为空
            {
             Hash[node->left]=new TreeNode(node->left->val);
             Hash[node]->left=Hash[node->left];
             //克隆并建立关系
             q.push(node->left);//左孩子加入队列中
            }
            if(node->right)
            {
             Hash[node->right]=new TreeNode(node->right->val);
             Hash[node]->right=Hash[node->right];
             //左孩子加入队列中
             q.push(node->right);
            }
        }
        return Hash[root];//走到这里说明关系已经全部弄好了返回克隆的头节点即可

    }

};

三.克隆含随机指针的二叉树

1485. 克隆含随机指针的二叉树 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

解题思路：

这题和上题就多了一个步骤，只需要在上题的基础之上，在遍历一次，由于已经建立好克隆节点和原节点之间的关系random指针也就非常的好克隆了。具体请看代码

对应代码：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     Node *left;
 *     Node *right;
 *     Node *random;
 *     Node() : val(0), left(nullptr), right(nullptr), random(nullptr) {}
 *     Node(int x) : val(x), left(nullptr), right(nullptr), random(nullptr) {}
 *     Node(int x, Node *left, Node *right, Node *random) : val(x), left(left), right(right), random(random) {}
 * };
 */

class Solution {
public:
    NodeCopy* copyRandomBinaryTree(Node* root) {
        if(root==nullptr)
         return nullptr;
         unordered_map<Node*,NodeCopy*>Hash;//建立映射关系
         queue<Node*>q;//用于宽度优先遍历
        Hash[root]=new NodeCopy(root->val);//建立克隆节点和原节点的映射关系
        q.push(root);//加入队列
        while(!q.empty())
        {
            auto node=q.front();
            q.pop();//从队列中取出一个节点
            if(node->left)
            {//有左孩子
              Hash[node->left]=new NodeCopy(node->left->val);
              Hash[node]->left=Hash[node->left];
              //建立映射和链接关系
              q.push(node->left);//左孩子加入队列中
            }
            if(node->right)
            {//右子树同理
             Hash[node->right]=new NodeCopy(node->right->val);
             Hash[node]->right=Hash[node->right];
              q.push(node->right);
            }
        }
        q.push(root);//在遍历一次克隆随机指针
        while(!q.empty())
        {
           auto node=q.front();
           q.pop();
           if(node->random)//如果随机指针不为空进行克隆
           {
             Hash[node]->random=Hash[node->random];
           }
           if(node->left)
           {
            q.push(node->left);
           }
           if(node->right)
           {
               q.push(node->right);
           }
        }
        return Hash[root];//克隆完成直接返回即可

    }
   
};

四.克隆N叉树

1490. 克隆 N 叉树 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

解题思路：

本题思路和上题基本一模一样，一张哈希表和一个队列进行宽度优先遍历即可。

对应代码：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    Node* cloneTree(Node* root) {
        if(root==nullptr)
        {
            return root;
        }
        unordered_map<Node*,Node*>Hash;//哈希表用于建立映射关系
        Hash[root]=new Node(root->val);
        queue<Node*>q;
        q.push(root);//将跟节点加入队列进行层序遍历
        while(!q.empty())
        {
         auto node=q.front();//从队列中取出头节点
            q.pop();

        for(auto x:node->children)//将其孩子节点全部克隆好
        {
            Hash[x]=new Node(x->val);//克隆
            Hash[node]->children.push_back(Hash[x]);//克隆
            q.push(x);
        }

         }
         return Hash[root];//克隆陈功返回头节点
    }
};

五.克隆图

133. 克隆图 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

解题思路：

1.使用一个哈希表Hash存储所有已被访问和克隆的节点。哈希表中的key是原始图中的节点，value是克隆图中的对应节点。
2.将题目给定的节点添加到队列。克隆该节点并存储到哈希表中。
3.每次从队列首部取出一个节点，遍历该节点的所有邻接点。如果某个邻接点已被访问，则该邻接点一定在Hash中，那么从Hash获得该邻接点，否则创建一个新的节点存储在Hash中，并将邻接点添加到队列。将克隆的邻接点添加到克隆图对应节点的邻接表中。重复上述操作直到队列为空，则整个图遍历结束。

对应代码：

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

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if(node==nullptr)
        {
            return nullptr;
        }
        queue<Node*>q;
        unordered_map<Node*,Node*>Hash;//建立映射关系
        Hash[node]=new Node(node->val);
        q.push(node);//进行宽度优先遍历
        while(!q.empty())
        {
          Node*temp=q.front();
          q.pop();
          for(auto x:temp->neighbors)//遍历其邻居
          {
              if(!Hash.count(x))//如果没有遍历过
              {
                  Hash[x]=new Node(x->val);//克隆
                  q.push(x);
              }
              Hash[temp]->neighbors.push_back(Hash[x]);//克隆
          }
        }
        return Hash[node];//克隆成功
        
    }
};