目录
一.复杂链表的复制
复制链表的复制由于之前以及写过了，在这里直接给出博客的链接。
二.克隆二叉树
题目描述：
?解题思路：
本题和上面那题的思路一样使用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];//走到这里说明关系已经全部弄好了返回克隆的头节点即可 } };
三.克隆含随机指针的二叉树
题目描述：
?解题思路：
这题和上题就多了一个步骤，只需要在上题的基础之上，在遍历一次，由于已经建立好克隆节点和原节点之间的关系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叉树
题目描述：
解题思路：
?本题思路和上题基本一模一样，一张哈希表和一个队列进行宽度优先遍历即可。
对应代码：
/* // 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];//克隆陈功返回头节点 } };
五.克隆图
题目描述：
解题思路：
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];//克隆成功 } };