深度优先搜索，再加判断就行了，用存储它的值，并且和是同步的，同时加减 。
剑指 Offer 35. 复杂链表的复制
/*// Definition for a Node.class Node {public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}};*/class Solution {public:Node* copyRandomList(Node* head) {if (head == NULL) {return head;}//复制节点Node *temp = head;while (temp) {Node *copyNode = new Node(temp->val);copyNode->next = temp->next;temp->next = copyNode;temp = temp->next->next;}//完成链表复制节点的随机指针复制temp = head;while (temp) {if (temp->random != NULL) {temp->next->random = temp->random->next;}temp = temp->next->next;}//将链表一分为二，删除原来的所有节点Node *newHead = head->next;temp = head->next;Node *mid = head;while (mid) {mid->next = mid->next->next;if (temp->next) {temp->next = temp->next->next;temp = temp->next;} else {temp->next = NULL;}mid = mid->next;}return newHead;}};
剑指 Offer 36. 二叉搜索树与双向链表
/*// Definition for a Node.class Node {public:int val;Node* left;Node* right;Node() {}Node(int _val) {val = _val;left = NULL;right = NULL;}Node(int _val, Node* _left, Node* _right) {val = _val;left = _left;right = _right;}};*/class Solution {public:Node *pre = NULL; //每次都指向root节点的前一个节点，它的第一次指向和fir相同Node *fir = NULL; //一直都指向的是最小数的位置Node* treeToDoublyList(Node* root) {if (!root) {return NULL;}dfs(root);pre->right = fir; //让尾节点，即最大值节点的right指向首节点，即最小值节点fir->left = pre; //让首节点，即最小值节点的left指向尾节点，即最大值节点return fir;}private://中序遍历真的很好用，它会返回一个有序序列，我们只需要补充中序操作就行了void dfs(Node *root) {if (!root) {return;}dfs(root->left);if (!pre) { //及遍历到了最左下的位置，也就是值最小的位置fir = root;} else { //紧接着的三步操作就和双指针一样，pre一直指向的是root前一个节点，因为我们使用的是递归操作，不用再考虑之后的访问问题，所以我们就直接可以进行交换节点的指向pre->right = root; //让前一个节点指向right指向当前节点rootroot->left = pre; //让当前节点的left指向前一个节点}pre = root; //原本指向前一个节点的指针指向当前节点dfs(root->right);}};
很玄幻，很妙，这个中序遍历，因为你之前已经递归到最小位置的节点了，所以你根本就不需要考虑后续怎么再返回上一个节点，你直接在中序的地方做你想要的操作就行了，这里root指向的是当前节点，而pre指向的是root的前一个节点，所以我们只需要将pre->right = root、root->left = pre这样就完成了这两个节点的双向链表的连接了，最后在记录下这个节点pre = root就好了，它就会一直递归上去，直到pre指向最后一个节点，即最大值节点，那么就剩一个问题了，怎么高效率的将头尾相连接起来，那么我们能想到，一开始的pre指向的是空，它直到访问到最小值节点，即头节点才会开始做中序的操作，那么这时候我们再定义一个指针fir一直指向这个头节点，最后直接对fir和pre进行连接操作岂不是快了很多，所以我们通过对pre的初值进行判空，若是空那么就表示才刚刚到达首节点，那么就赋值就行了，这样就记录下来这个节点了，最后通过pre->right = fir、fir->left = pre就完成了 。
剑指 Offer 37. 序列化二叉树
/*** Definition for a binary tree node.* struct TreeNode {*int val;*TreeNode *left;*TreeNode *right;*TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Codec {public:// Encodes a tree to a single string.string serialize(TreeNode* root) {if (root == nullptr) {return "";}queue q;q.push(root);string ans;while (!q.empty()) {TreeNode* t = q.front();q.pop();if (t == nullptr) {ans += "#,";} else {ans += to_string(t->val) + ',';q.push(t->left);q.push(t->right);}}return ans;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if (data.length() == 0) {return nullptr;}vector myVector;int idx = 0;//将节点都存入数组中while (idx