[数据结构与算法]刷题《剑指Offer》day14

题目来源：力扣《剑指Offer》第二版
完成时间：2022/08/09

35. 复杂链表的复制

题目链接：剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode）

我的题解

这题的思路不难理解。

分三步，第一步是遍历链表，将每个节点都复制一遍，并且用next连接在原节点的后面。

第二步再次遍历链表，复制每个节点的random指针

第三步很重要，把链表拆分成两部分。这里要注意，必须拆分干净，要把原来的链表也要还原，不能只拆新的出来。不然就会报错…

最后返回新链表头节点即可。

/*
// 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 NULL;
        Node* tmp = head;
        while(tmp != NULL) {
            Node* copy = new Node(tmp->val);
            copy->next = tmp->next;
            tmp->next = copy;
            tmp = copy->next;
        }
        tmp = head;
        while(tmp != NULL) {
            if(tmp->random != NULL)
                tmp->next->random = tmp->random->next;
            tmp = tmp->next->next;
        }

        Node* copyhead = head->next;
        tmp = head->next;
        Node* origin = head;
        while(origin != NULL) {
            origin->next = origin->next->next;
            origin = origin->next;
            if(tmp->next != NULL){
                tmp->next = tmp->next->next;
                tmp = tmp->next;
            }
        }

        return copyhead;
    }
};

36. 二叉搜索树与双向链表

题目链接：剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（LeetCode）

我的题解

这题要借助栈来辅助操作，因为二叉搜索树的中序遍历刚好是从小到大排列的，符合题意。所以可以先中序遍历一遍二叉树，用栈存储每个结果，最后挨个处理一下每个节点关系就行。

/*
// 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:
    void traverse(Node* node,queue<Node*>& que) {
        if(node->left) traverse(node->left,que);
        que.push(node);
        if(node->right) traverse(node->right,que);
    }

    Node* treeToDoublyList(Node* root) {
        if(root == NULL) return NULL;
        queue<Node*> que;
        traverse(root,que);
        Node* head = que.front();
        Node* cur = que.front();
        que.pop();
        while(!que.empty()) {
            Node* tmp = que.front();
            que.pop();
            cur->right = tmp;
            tmp->left = cur;
            cur = tmp;
        }
        cur->right = head;
        head->left = cur;
        return head;
    }
};