题目链接：随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
  你的代码 只 接受原链表的头节点 head 作为传入参数。

方法一：哈希表

/*
// 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;
        unordered_map<Node*,Node*> map;

        Node* cur = head;
        while (cur != NULL) {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }

        cur = head;
        while (cur != NULL) {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        return map[head];
    }
};

方法二：拼接+拆分

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        // 1. 复制各节点，并构建拼接链表
        while(cur != nullptr) {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while(cur != nullptr) {
            if(cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 3. 拆分两链表
        cur = head->next;
        Node* pre = head, *res = head->next;
        while(cur->next != nullptr) {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr; // 单独处理原链表尾节点
        return res;      // 返回新链表头节点
    }
};

题目链接：LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

方法一：双向链表

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache_list; // pair 里面保存的是 key 和 value
    unordered_map<int, list<pair<int, int>>::iterator> key_to_iter; // key -> 链表节点迭代器

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto umap_iter = key_to_iter.find(key);
        if (umap_iter == key_to_iter.end()) { // 没有这本书
            return -1;
        }
        auto list_iter = umap_iter->second; // 有这本书
        // 把这本书（list_iter）从书堆（cache_list）中抽出来，放到最上面（cache_list.begin()）
        cache_list.splice(cache_list.begin(), cache_list, list_iter);
        return list_iter->second; // 返回这本书的 value
    }

    void put(int key, int value) {
        auto umap_iter = key_to_iter.find(key);
        if (umap_iter != key_to_iter.end()) { // 有这本书
            auto list_iter = umap_iter->second;
            list_iter->second = value; // 更新 value
            // 把这本书（list_iter）从书堆（cache_list）中抽出来，放到最上面（cache_list.begin()）
            cache_list.splice(cache_list.begin(), cache_list, list_iter);
            return;
        }
        // 新书，放到最上面（emplace_front）
        cache_list.emplace_front(key, value);
        key_to_iter[key] = cache_list.begin();
        // 书太多了
        if (key_to_iter.size() > capacity) {
            // 去掉最后一本书
            key_to_iter.erase(cache_list.back().first);
            cache_list.pop_back();
        }
    }
};

题目链接：二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        if (root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);

        if (left && right) return root;
        return left ? left : right;
    }
};

方法二：栈

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        unordered_map<TreeNode*,TreeNode*> parent;
        parent[root] = NULL;

        stack<TreeNode*> s;
        s.push(root);
        while (!parent.count(p) || !parent.count(q)) {
            TreeNode* cur = s.top();
            s.pop();
            if (cur->left) {
                parent[cur->left] = cur;
                s.push(cur->left);
            }
            if (cur->right) {
                parent[cur->right] = cur;
                s.push(cur->right);
            }
        }
        unordered_set<TreeNode*> se;
        while (p) {
            se.insert(p);
            p = parent[p];
        }
        while (!se.count(q)) {
            q = parent[q];
        }
        return q;
    }
};

题目链接：从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0) return nullptr;
        TreeNode* root = new TreeNode(preorder[0]);
        int mid = 0;
        while (mid < inorder.size() && inorder[mid] != preorder[0]) {
            mid++;
        }

        vector<int> leftIn(inorder.begin(), inorder.begin() + mid);
        vector<int> rightIn(inorder.begin() + mid + 1, inorder.end());

        vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + mid);
        vector<int> rightPre(preorder.begin() + 1 + mid, preorder.end());

        root->left = buildTree(leftPre,leftIn);
        root->right = buildTree(rightPre,rightIn);
        return root;
    }
};

题目链接：二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr) return ;
        flatten(root->left);
        flatten(root->right);
        if (root->left != nullptr) {
            auto pre = root->left;
            while (pre->right != nullptr) pre = pre->right;
            pre->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }
        root = root->right;
        return ;
    }
};