算法周报-01

前言：

这一周学了挺多

常见九种排序
堆结构
位运算与位图
链表相关题目
数据结构相关题目
二叉树相关题目
递归相关
对于常见九种排序，没啥好说的，剥离三傻排序基本上O(nlbn)就是上限了，剩余的就是拿空间换稳定性了，而对于O(n)的非比较排序来说，则对于数据的结构有很大要求。

堆结构是一个需要O(lbn)来调整的结构，从底至顶建堆的性能比从顶至底建堆更快，因为减少了向下伸展的层数。

位运算基本上算是常数时间最好的运算，位图多用于进行状态记录。

链表相关题目基本上考的就是码力。

数据结构类型题目则大多要求维护一个带有特殊性质的数据结构，类似维护一个随时求中位数的结构可以使用双堆法构建。

二叉树相关题目基本上就是BFS和DFS，对于DFS而言，也就是利用好递归的性质，对于递归形成的独立空间如何利用，递归结束传递的值如何利用等。

递归类型题单

1. 字符串的全部子序列

思路：
- 利用递归生成所有子序列。
- 对于字符串中的每个字符，做“选择”或“不选择”的决策。
- 递归结束时，将当前形成的子序列加入去重集合中。

题解：

// 字符串的全部子序列
// 子序列本身是可以有重复的，只是这个题目要求去重
// 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
class Solution1 {
private:
    unordered_set<string> set; // 用于存储所有唯一的子序列
public:
    vector<string> generatePermutation(string& str) {
        set.clear();
        string path;
        f(str, 0, path);
        return vector<string>(set.begin(), set.end()); // 直接用 set 初始化 vector
    }
    // 递归生成子序列
    void f(string& s, int i, string& path) {
        if (i == s.length()) {
            set.insert(path); // 将当前 path 作为一个子序列加入集合
            return;
        }
        // 选择当前字符
        path.push_back(s[i]);
        f(s, i + 1, path);
        path.pop_back(); // 回溯

        // 不选择当前字符
        f(s, i + 1, path);
    }
};

2. 含重复元素的子集（Subsets II）

思路：
- 先对数组排序，以便相同元素相邻，便于剪枝去重。
- 在递归过程中，遇到连续重复的元素时，跳过部分决策，避免产生重复组合。
- 有两种写法：
  - 第一种：在递归中先跳过重复，再选择 1 到 (重复个数) 个当前数字；
  - 第二种：利用记录上一个值的方式，在同一层循环中防止重复选择。

题解：

// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的组合
// 答案 不能 包含重复的组合。返回的答案中，组合可以按 任意顺序 排列
// 测试链接 : https://leetcode.cn/problems/subsets-ii/
class Solution2 {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 先排序，方便去重
        vector<vector<int>> ans;
        vector<int> path;
        f(nums, 0, path, ans);
        return ans;
    }

    void f(vector<int>& nums, int i, vector<int>& path, vector<vector<int>>& ans) {
        if (i == nums.size()) {
            ans.push_back(path);
            return;
        }

        // 跳到下一个组第一个数
        int j = i + 1;
        while (j < nums.size() && nums[i] == nums[j]) {
            ++j;
        }

        // 不选择当前数
        f(nums, j, path, ans);

        // 选择 1 到 (j - i) 个当前数字
        for (int count = 1; count <= (j - i); ++count) {
            path.push_back(nums[i]); // 选择当前数
            f(nums, j, path, ans);
        }

        // 回溯，恢复 path
        path.resize(path.size() - (j - i)); // 恢复 path 之前的状态
    }
};

3. 没有重复项数字的全排列

思路：
- 采用标准的递归回溯方法，每一层通过 for 循环选择一个数字。
- 通过交换操作在原数组上“收割”答案，保证排列的生成。
- 另有旧解法利用数组做哈希记录，防止重复使用数字。

题解：

// 没有重复项数字的全排列
// 测试链接 : https://leetcode.cn/problems/permutations/
class Solution3 {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        f(nums, 0, ans);
        return ans;
    }
    void f(vector<int>& nums, int i, vector<vector<int>>& ans) {
        if (i == nums.size()) {
            vector<int> cur;
            for (int num : nums) {
                cur.push_back(num);
            }
            ans.push_back(cur);
        } else {
            for (int j = i; j < nums.size(); ++j) {
                // 交换使得当前的 j 处的数字来到 i 位置后，后续数字依次尝试
                swap(nums, i, j);
                f(nums, i + 1, ans);
                // 回溯恢复现场
                swap(nums, i, j);
            }
        }
    }
    void swap(vector<int>& nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};

4. 有重复项数组的去重全排列

思路：
- 与无重复全排列思路类似，但在同一层递归中利用 unordered_set 保证每个数字只在当前位置出现一次。
- 另一种旧解法通过 set 过滤重复的排列。

题解：

// 有重复项数组的去重全排列
// 测试链接 : https://leetcode.cn/problems/permutations-ii/
class Solution4 {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        f(nums, 0, ans);
        return ans;
    }
    void f(vector<int>& nums, int i, vector<vector<int>>& ans) {
        if (i == nums.size()) {
            vector<int> cur;
            for (int num : nums) {
                cur.push_back(num);
            }
            ans.push_back(cur);
        } else {
            unordered_set<int> set;
            for (int j = i; j < nums.size(); ++j) {
                // 仅当当前数值未出现在 i 位置时尝试交换
                if (set.find(nums[j]) == set.end()) {
                    set.insert(nums[j]);
                    swap(nums, i, j);
                    f(nums, i + 1, ans);
                    swap(nums, i, j);
                }
            }
        }
    }
    void swap(vector<int>& nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};

5. 用递归函数逆序栈

思路：
- 递归地移除栈顶元素，直到栈空，此时返回最底部元素。
- 在返回过程中，将之前弹出的元素依次压回栈中，使得原栈顺序反转。

题解：

// 用递归函数逆序栈
class Solution5 {
public:
    void reverse(stack<int>& stack) {
        if (!stack.empty()) {
            int num = bottomOut(stack);
            reverse(stack);
            stack.push(num);
        }
    }
    // 作用：移除并返回栈底元素，上面的元素依次下移
    int bottomOut(stack<int>& stack) {
        int ret = stack.top();
        stack.pop();
        if (stack.empty()) {
            return ret;
        } else {
            int last = bottomOut(stack);
            stack.push(ret);
            return last;
        }
    }
};

6. 用递归函数排序栈

思路：
- 仅使用栈的 push、pop、isEmpty 方法以及递归函数完成排序。
- 定义辅助函数：
  - deep：递归求栈的深度（不改变栈中数据顺序）。
  - max：在不改变栈状态的前提下求出当前深度范围内的最大值。
  - times：统计当前深度范围内最大值出现的次数。
  - down：将这若干个最大值“下沉”到栈底，保持其他元素的相对顺序。
- 通过多次调整，使得最终从栈顶到栈底依次为从小到大的顺序。

题解：

// 用递归函数排序栈
// 仅能使用栈的 push、pop、isEmpty 方法以及递归函数
class Solution6 {
public:
    // 直接在传入的栈上递归完成排序
    // 排序后，从栈顶到栈底依次为从小到大
    void sort(stack<int>& st) {
        int d = deep(st);
        while (d > 0) {
            int m = max(st, d);
            int k = times(st, d, m);
            down(st, d, m, k);
            d -= k;
        }
    }
private:
    // 返回栈的深度，不改变栈中数据顺序
    int deep(stack<int>& st) {
        if (st.empty()) {
            return 0;
        }
        int num = st.top();
        st.pop();
        int d = deep(st) + 1;
        st.push(num);
        return d;
    }
    // 在当前深度范围内返回最大值，不改变栈状态
    int max(stack<int>& st, int deepCount) {
        if (deepCount == 0) {
            return INT_MIN;
        }
        int num = st.top();
        st.pop();
        int restMax = max(st, deepCount - 1);
        int maxVal = (num > restMax ? num : restMax);
        st.push(num);
        return maxVal;
    }
    // 统计当前深度范围内最大值出现的次数
    int times(stack<int>& st, int deepCount, int maxVal) {
        if (deepCount == 0) {
            return 0;
        }
        int num = st.top();
        st.pop();
        int count = times(st, deepCount - 1, maxVal) + (num == maxVal ? 1 : 0);
        st.push(num);
        return count;
    }
    // 将深度范围内的 k 个最大值下沉到栈底，保持其他元素相对顺序
    void down(stack<int>& st, int deepCount, int maxVal, int k) {
        if (deepCount == 0) {
            // 到达递归底部，压入 k 个最大值
            for (int i = 0; i < k; i++) {
                st.push(maxVal);
            }
        } else {
            int num = st.top();
            st.pop();
            down(st, deepCount - 1, maxVal, k);
            if (num != maxVal) {
                st.push(num);
            }
        }
    }
};

7. 打印 n 层汉诺塔问题的最优移动轨迹

思路：
- 使用递归解决汉诺塔问题。
- 辅助函数接收参数：盘子数量、起始柱子、目标柱子、辅助柱子。
- 当盘子数为 1 时，直接移动；否则先将上面 n-1 个盘子移动到辅助柱子，再将第 n 个盘子移动到目标柱子，最后将那 n-1 个盘子从辅助柱子移动到目标柱子。

题解：

// 打印 n 层汉诺塔问题的最优移动轨迹
class Solution7 {
public:
    void hanoi(int n) {
        if (n > 0) {
            f(n, "左", "右", "中");
        }
    }
private:
    // 辅助函数：
    // i：盘子的数量
    // from：起始柱子，to：目标柱子，other：辅助柱子
    void f(int i, const string &from, const string &to, const string &other) {
        if (i == 1) {
            cout << "移动圆盘 1 从 " << from << " 到 " << to << endl;
        } else {
            f(i - 1, from, other, to);
            cout << "移动圆盘 " << i << " 从 " << from << " 到 " << to << endl;
            f(i - 1, other, to, from);
        }
    }
};

8. 含有嵌套的表达式求值

思路：
- 通过递归解析表达式，同时维护两个容器（一个存放数字、一个存放操作符）。
- 遇到数字则进行累加；遇到操作符（+、-、*、/）则调用辅助函数进行计算。
- 当遇到左括号时，递归处理子表达式，遇到右括号则结束当前递归。
- 最终将所有数字和操作符合并计算得到结果。

题解：

// 含有嵌套的表达式求值
// 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/
class Solution8 {
public:
    int where = 0;

    int compute(vector<int>& numbers, vector<char>& ops) {
        int n = numbers.size();
        int ans = numbers[0];
        for (int i = 1; i < n; i++) {
            ans += (ops[i - 1] == '+') ? numbers[i] : -numbers[i];
        }
        return ans;
    }

    void push(vector<int>& numbers, vector<char>& ops, int cur, char op) {
        int n = numbers.size();
        if (n == 0 || ops[n - 1] == '+' || ops[n - 1] == '-') {
            numbers.push_back(cur);
            ops.push_back(op);
        } else {
            int topNumber = numbers[n - 1];
            char topOp = ops[n - 1];
            if (topOp == '*') {
                numbers[n - 1] = topNumber * cur;
            } else {
                numbers[n - 1] = topNumber / cur;
            }
            ops[n - 1] = op;
        }
    }

    int f(const string& s, int i) {
        int cur = 0;
        vector<int> numbers;
        vector<char> ops;
        while (i < s.length() && s[i] != ')') {
            if (s[i] >= '0' && s[i] <= '9') {
                cur = cur * 10 + s[i] - '0';
                i++;
            } else if (s[i] != '(') {
                // 遇到操作符 + - * /
                push(numbers, ops, cur, s[i]);
                cur = 0;
                i++;
            } else {
                // 遇到 '('
                cur = f(s, i + 1);
                i = where + 1;
            }
        }
        push(numbers, ops, cur, '+');
        where = i;
        return compute(numbers, ops);
    }

    int calculate(const string& str) {
        where = 0;
        return f(str, 0);
    }
};

9. 含有嵌套的字符串解码

思路：
- 利用递归解析字符串。
- 遍历过程中遇到字母直接拼接；遇到数字时累计重复次数；遇到 [ 后递归解码内部字符串，遇到 ] 则返回。
- 使用辅助函数将解码后的字符串按计数重复拼接。

题解：

// 含有嵌套的字符串解码
// 测试链接 : https://leetcode.cn/problems/decode-string/
class Solution9 {
public:
    string decodeString(string s) {
        where = 0;
        return f(s, 0);
    }
private:
    int where;
    string f(string &s, int i) {
        stringstream path;
        int cnt = 0;
        while (i < s.length() && s[i] != ']') {
            if (('a' <= s[i] && s[i] <= 'z') || ('A' <= s[i] && s[i] <= 'Z')) {
                path << s[i++];
            } else if ('0' <= s[i] && s[i] <= '9') {
                cnt = cnt * 10 + s[i++] - '0';
            } else {
                path << get(cnt, f(s, i + 1));
                i = where + 1;
                cnt = 0;
            }
        }
        where = i;
        return path.str();
    }
    string get(int cnt, string str) {
        stringstream ss;
        for (int i = 0; i < cnt; ++i) {
            ss << str;
        }
        return ss.str();
    }
};

10. 含有嵌套的分子式求原子数量

思路：
- 利用递归解析化学分子式。
- 遇到大写字母或左括号时开始记录元素名称或递归解析嵌套部分。
- 数字用于确定当前元素或嵌套部分的倍数（若数字为 0 则默认为 1）。
- 最终返回一个有序 map，记录每种原子的累计数量；输出时数量大于 1 时附带数字。

题解：

// 含有嵌套的分子式求原子数量
// 测试链接 : https://leetcode.cn/problems/number-of-atoms/
class Solution10 {
public:
    string countOfAtoms(string str) {
        where = 0;
        map<string, int> map = f(str, 0);
        stringstream ans;
        for (auto &it : map) {
            ans << it.first;
            if (it.second > 1) ans << it.second;  // 仅在数量大于 1 时输出
        }
        return ans.str();
    }
private:
    int where;
    // 从 s[i...] 开始计算，遇到终止或 ')' 停止
    // 返回当前段的元素计数结果，同时更新全局变量 where
    map<string, int> f(string &s, int i) {
        map<string, int> ans;
        stringstream name;
        map<string, int> pre;
        int cnt = 0;
        while (i < s.length() && s[i] != ')') {
            if (('A' <= s[i] && s[i] <= 'Z') || (s[i] == '(')) {
                fill(ans, name, pre, cnt);
                name.str("");  // 清空 name
                name.clear();
                cnt = 0;
                if ('A' <= s[i] && s[i] <= 'Z') {
                    name << s[i++];
                } else {
                    pre = f(s, i + 1);
                    i = where + 1;
                }
            } else if ('a' <= s[i] && s[i] <= 'z') {
                name << s[i++];
            } else {
                cnt = cnt * 10 + s[i++] - '0';
            }
        }
        fill(ans, name, pre, cnt);
        where = i;
        return ans;
    }

    void fill(map<string, int> &ans, stringstream &name, map<string, int> &pre, int cnt) {
        if (name.str().length() > 0 || !pre.empty()) {
            cnt = (cnt == 0 ? 1 : cnt);
            if (name.str().length() > 0) {
                string key = name.str();
                ans[key] += cnt;  // 累加相同元素
            } else {
                for (auto &it : pre) {
                    ans[it.first] += it.second * cnt;
                }
            }
        }
    }
};

11. N 皇后问题

思路：
- 提供两种解法：
  - 常规回溯法：逐行放置皇后，每次检查是否与前面已放置的皇后冲突（同列或对角线冲突）。
  - 位运算优化法：
    - 利用位运算标记已占用的列、左对角线和右对角线。
    - 计算当前可放置皇后的候选位置，利用“提取最右侧的1”的技巧递归求解。
    - 这种方法能大幅提高搜索效率。

题解：

// N皇后问题
// 测试链接 : https://leetcode.cn/problems/n-queens-ii/
class Solution11 {
public:
    // 常规回溯法
    int totalNQueens1(int n) {
        if (n < 1) {
            return 0;
        }
        vector<int> path(n, 0); // 预分配 n 个元素
        return f1(0, path, n);
    }
    // 位运算法，效率更高
    int totalNQueens2(int n) {
        if (n < 1) {
            return 0;
        }
        int limit = (1 << n) - 1;
        return f2(limit, 0, 0, 0);
    }
    void runTest() {
        try {
            int N = 14;
            // 计时常规回溯法
            auto start1 = std::chrono::high_resolution_clock::now();
            int result1 = totalNQueens1(N);
            auto end1 = std::chrono::high_resolution_clock::now();
            auto duration1 = std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start1).count();

            // 计时位运算法
            auto start2 = std::chrono::high_resolution_clock::now();
            int result2 = totalNQueens2(N);
            auto end2 = std::chrono::high_resolution_clock::now();
            auto duration2 = std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count();

            // 输出结果和运行时间
            cout << "totalNQueens1(" << N << "): " << result1 << " (" << duration1 << " ms)" << endl;
            cout << "totalNQueens2(" << N << "): " << result2 << " (" << duration2 << " ms)" << endl;
        } catch (const exception& e) {
            cout << e.what() << endl;
        }
    }
private:
    int f1(int i, vector<int>& path, int n) {
        if (i == n) {
            return 1;
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            if (check(path, i, j)) {
                path[i] = j;
                ans += f1(i + 1, path, n);
            }
        }
        return ans;
    }
    bool check(vector<int>& path, int i, int j) {
        for (int k = 0; k < i; ++k) {
            if (j == path[k] || abs(i - k) == abs(j - path[k])) {
                return false;
            }
        }
        return true;
    }
    // 位运算法辅助函数
    int f2(int limit, int col, int left, int right) {
        if (col == limit) {
            return 1;
        }
        int ban = col | left | right;
        int candidate = limit & (~ban);
        int ans = 0;
        while (candidate != 0) {
            int place = candidate & (-candidate);
            candidate ^= place;
            ans += f2(limit, col | place, (int)((unsigned int)(left | place) >> 1), (right | place) << 1);
        }
        return ans;
    }
};

二叉树题单

1. 二叉树的层序遍历

思路：
- 采用层序遍历一次处理一层，每层先记录当前层的节点数，再依次处理。
- 将当前层所有节点的值存入结果数组，同时将下一层节点加入队列。

题解：

// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if (root == nullptr) {
        return ans;
    }
    
    vector<TreeNode*> queue(MAXN);
    int l = 0, r = 0;
    queue[r++] = root;
    
    while (l < r) {
        int size = r - l;
        vector<int> list;
        
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = queue[l++];  // 获取当前节点并更新左指针
            list.push_back(cur->val);
            
            if (cur->left != nullptr) {
                queue[r++] = cur->left;
            }
            if (cur->right != nullptr) {
                queue[r++] = cur->right;
            }
        }
        
        ans.push_back(list);  // 添加当前层结果
    }
    
    return ans;
}

2. 二叉树的锯齿形层序遍历

思路：
- 基于层序遍历，通过一个标志位（isReverse）判断当前层的输出顺序。
- 当 isReverse 为 true 时，从队列尾部逆序输出当前层节点的值。

题解：

// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if (root == nullptr) {
        return ans;
    }
    
    vector<TreeNode*> queue(MAXN);
    int l = 0, r = 0;
    queue[r++] = root;
    bool isReverse = false;
    while (l < r) {
        int size = r - l;
        vector<int> list;
        // 根据 isReverse 决定遍历顺序
        for (int i = isReverse ? r - 1 : l, j = isReverse ? -1 : 1, k = 0; k < size; i += j, ++k) {
            TreeNode* cur = queue[i];
            list.push_back(cur->val);
        }
        // 标准层序遍历，扩充下一层
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = queue[l++];
            if (cur->left != nullptr) {
                queue[r++] = cur->left;
            }
            if (cur->right != nullptr) {
                queue[r++] = cur->right;
            }
        }
        isReverse = !isReverse;
        ans.push_back(list);
    }
    return ans;
}

3. 二叉树的最大特殊宽度

思路：
- 利用层序遍历时给每个节点分配编号：对于满二叉树，
  - 左孩子编号为父节点编号的两倍，
  - 右孩子为两倍加一。
- 每层宽度为该层最后节点编号与第一个节点编号之差加 1。

题解：

// 二叉树的最大特殊宽度
// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/
int widthOfBinaryTree(TreeNode* root) {
    int ans = 1;
    int l = 0, r = 0;
    vector<pair<TreeNode*, int>> queue(MAXN);
    queue[r++] = pair<TreeNode*, int>{root, 1};
    while (l < r) {
        int size = r - l;
        ans = max(ans, queue[r - 1].second - queue[l].second + 1);
        for (int i = 0; i < size; ++i) {
            TreeNode* node = queue[l].first;
            int id = queue[l++].second;
            if (node->left != nullptr) {
                queue[r++] = pair<TreeNode*, int>{node->left, id * 2};
            }
            if (node->right != nullptr) {
                queue[r++] = pair<TreeNode*, int>{node->right, id * 2 + 1};
            }
        }
    }
    return ans;
}

4. 求二叉树的最大、最小深度

思路：
- 最大深度： 递归求左右子树深度，取较大者加 1。
- 最小深度： 对于叶节点返回 1，对于只有一侧为空的情况分别处理后取较小值加 1。

题解：

// 最大深度
// 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
int maxDepth(TreeNode* root) {
    return root == nullptr ? 0 : max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
// 最小深度
// 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/
int minDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    int ldepp = INT_MAX;
    int rdepp = INT_MAX;
    if (root->left != nullptr) {
        ldepp = minDepth(root->left);
    }
    if (root->right != nullptr) {
        rdepp = minDepth(root->right);
    }
    return min(ldepp, rdepp) + 1;
}

5. 二叉树先序序列化和反序列化

思路：
- 序列化： 利用先序遍历将树转换为字符串，空节点用“#”标记。
- 反序列化： 根据字符串分割后的序列，递归构造二叉树。

题解：

// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
string serialize(TreeNode* root) {
    stringstream ans;
    deserializeHelper(root, ans);
    return ans.str();
}
void deserializeHelper(TreeNode* root, stringstream& ss) {
    if (root == nullptr) {
        ss << "#,";
    } else {
        ss << root->val << ",";
        deserializeHelper(root->left, ss);
        deserializeHelper(root->right, ss);
    }
}
// 反序列化：将字符串转换回二叉树
TreeNode* deserialize(string data) {
    vector<string> res;
    stringstream ss(data);
    string token;
    while(getline(ss, token, ',')) {
        res.push_back(token);
    }
    cnt = 0;
    return deserializeHelper(res);
}
TreeNode* deserializeHelper(vector<string> const& strings) {
    string cur = strings[cnt++];
    if (cur == "#") {
        return nullptr;
    } else {
        TreeNode* head = new TreeNode(stoi(cur));
        head->left = deserializeHelper(strings);
        head->right = deserializeHelper(strings);
        return head;
    }
}

6. 二叉树按层序列化和反序列化

思路：
- 序列化： 采用层序遍历将节点值转换为字符串，空节点标记为“#”。
- 反序列化： 利用队列按照层次构造二叉树。

题解：

string serializeUsedLevelOrder(TreeNode* root) {
    if (!root) return "";
    stringstream ss;
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node) {
            ss << node->val << ",";  // 存储节点值
            q.push(node->left);
            q.push(node->right);
        } else {
            ss << "#,";
        }
    }
    return ss.str();
}
TreeNode* deserializeUsedLevelOrder(string data) {
    if (data.empty()) return nullptr;
    
    stringstream ss(data);
    string token;
    queue<TreeNode*> q;

    // 读取根节点
    getline(ss, token, ',');
    TreeNode* root = new TreeNode(stoi(token));
    q.push(root);

    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();

        // 处理左子节点
        if (getline(ss, token, ',')) {
            if (token != "#") {
                node->left = new TreeNode(stoi(token));
                q.push(node->left);
            }
        }

        // 处理右子节点
        if (getline(ss, token, ',')) {
            if (token != "#") {
                node->right = new TreeNode(stoi(token));
                q.push(node->right);
            }
        }
    }
    return root;
}

7. 利用先序与中序遍历序列构造二叉树

思路：
- 利用先序遍历确定根节点，在中序遍历中找到根节点位置，从而划分左右子树。
- 递归构造左右子树直至整棵树复原。

题解：

// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.size() == 0 || inorder.size() == 0 || preorder.size() != inorder.size()) {
        return nullptr;
    }        
    unordered_map<int, int> map;
    for (int i = 0; i < inorder.size(); ++i) {
        map[inorder[i]] = i;
    }
    return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, map);
}
TreeNode* buildTreeHelper(vector<int>& pre, int l1, int r1, vector<int>& in, int l2, int r2, unordered_map<int, int>& map) {
    if (l1 > r1) {
        return nullptr;
    }
    TreeNode* head = new TreeNode(pre[l1]);
    if (l1 == r1) {
        return head;
    }
    int k = map[pre[l1]];
    head->left = buildTreeHelper(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, map);
    head->right = buildTreeHelper(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);
    return head;
}

8. 验证完全二叉树

思路：
- 利用层序遍历检测完全二叉树的特点：
  1. 不能出现“右子节点存在而左子节点为空”；
  2. 一旦出现节点缺失子节点，后续所有节点必须均为叶节点。

题解：

// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
bool isCompleteTree(TreeNode* root) {
    vector<TreeNode*> queue(101);
    int l, r;
    if (root == nullptr) {
        return true;
    }
    l = r = 0;
    queue[r++] = root;
    bool leaf = false;
    while (l < r) {
        root = queue[l++];
        if ((root->left == nullptr && root->right != nullptr) || (leaf && (root->left != nullptr || root->right != nullptr))) {
            return false;
        }
        if (root->left != nullptr) {
            queue[r++] = root->left;
        }
        if (root->right != nullptr) {
            queue[r++] = root->right;
        }
        if (root->left == nullptr || root->right == nullptr) {
            leaf = true;
        }
    }
    return true;
}

9. 求完全二叉树的节点个数

思路：
- 采用递归的方法，通过计算左子树最左侧的高度判断右子树是否满，进而确定节点数。
- 复杂度为 O((h)^2)。

题解：

// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/
int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return countNodesHelper(root, 1, countNodesHelperMostLeft(root, 1));
}
int countNodesHelper(TreeNode* cur, int level, int h) {
    if (level == h) {
        return 1;
    }
    if (countNodesHelperMostLeft(cur->right, level + 1) == h) {
        // cur右子树最左侧达到了最深层
        return (1 << (h - level)) + countNodesHelper(cur->right, level + 1, h);
    } else {
        // 否则，计算左子树节点数
        return (1 << (h - level - 1)) + countNodesHelper(cur->left, level + 1, h);
    }
}
int countNodesHelperMostLeft(TreeNode* cur, int level) {
    while (cur != nullptr) {
        level++;
        cur = cur->left;
    }
    return level - 1;
}

10. 普通二叉树上寻找两个节点的最近公共祖先

思路：
- 利用后序遍历，如果当前节点为 p 或 q，返回该节点；
- 否则判断左右子树是否同时包含 p 和 q，若是则当前节点为 LCA，否则返回非空的一侧。

题解：

// 普通二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr || root == p || root == q) {
        return root;
    }
    TreeNode* l = lowestCommonAncestor(root->left, p, q);
    TreeNode* r = lowestCommonAncestor(root->right, p, q);
    if (l != nullptr && r != nullptr) {
        return root;
    }
    return l != nullptr ? l : r;
}

11. 搜索二叉树上寻找两个节点的最近公共祖先

思路：
- 利用 BST 的性质，若当前节点介于 p 和 q 之间则为 LCA；
- 否则若当前节点小于两者，则进入右子树，若大于两者，则进入左子树。

题解：

// 搜索二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
TreeNode* lowestCommonAncestorOnBST(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root->val != p->val && root->val != q->val) {
        if (min(p->val, q->val) < root->val && root->val < max(p->val, q->val)) {
            break;
        }
        root = root->val < min(p->val, q->val) ? root->right : root->left;
    }
    return root;
}

12. 收集累加和等于 aim 的所有路径

思路：
- 使用回溯从根到叶子路径累计求和；
- 当累加和等于目标且达到叶节点时，记录当前路径；回溯时撤销选择。

题解：

// 收集累加和等于aim的所有路径
// 测试链接 : https://leetcode.cn/problems/path-sum-ii/
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>> ans;
    if (root != nullptr) {
        vector<int> path;
        pathSumHelper(path, ans, root, targetSum, 0);
    }
    return ans;
}
void pathSumHelper(vector<int>& path, vector<vector<int>>& ans, TreeNode* cur, int aim, int sum) {
    path.push_back(cur->val);
    if (cur->left == nullptr && cur->right == nullptr) {
        if (cur->val + sum == aim) {
            ans.push_back(path);
        }
    } else {
        if (cur->left != nullptr) {
            pathSumHelper(path, ans, cur->left, aim, sum + cur->val);
        }
        if (cur->right != nullptr) {
            pathSumHelper(path, ans, cur->right, aim, sum + cur->val);
        }
    }
    path.pop_back();
}

13. 验证平衡二叉树

思路：
- 利用树形 DP，自底向上计算左右子树高度；
- 若任一节点左右子树高度差大于 1，则标记为不平衡。

题解：

// 验证平衡二叉树
// 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/
bool isBalanced(TreeNode* root) {
    bool isBalanced = true;
    isBalancedHelper4ReturnHeight(root, isBalanced);
    return isBalanced;
}
int isBalancedHelper4ReturnHeight(TreeNode* cur, bool& isBalanced) {
    if (!isBalanced || cur == nullptr) {
        return 0;
    }
    int lh = isBalancedHelper4ReturnHeight(cur->left, isBalanced);
    int rh = isBalancedHelper4ReturnHeight(cur->right, isBalanced);
    if (abs(lh - rh) > 1) {
        isBalanced = false;
    }
    return max(lh, rh) + 1;
}

14. 验证搜索二叉树

思路：
- 方法一：中序遍历后检查是否严格升序；
- 方法二：递归验证，每个节点需满足左子树最大值 < 当前值 < 右子树最小值。

题解：

// 验证搜索二叉树
// 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/
bool isValidBST(TreeNode* root) {
    long min = LONG_MIN, max = LONG_MAX;
    bool isValid = true;
    isValidBSTHelper(root, min, max, isValid);
    return isValid;
}
void isValidBSTHelper(TreeNode* head, long& min, long& max, bool& isValid) {
    if (!isValid) return;
    if (head == nullptr) {
        min = LONG_MAX;
        max = LONG_MIN;
        return;
    }
    
    long leftMin = LONG_MAX, leftMax = LONG_MIN;
    long rightMin = LONG_MAX, rightMax = LONG_MIN;
    
    isValidBSTHelper(head->left, leftMin, leftMax, isValid);
    if (leftMax != LONG_MIN && !(leftMax < head->val)) {
        isValid = false;
        return;
    }
    
    isValidBSTHelper(head->right, rightMin, rightMax, isValid);
    if (rightMin != LONG_MAX && !(head->val < rightMin)) {
        isValid = false;
        return;
    }
    
    min = (head->left == nullptr) ? head->val : std::min(leftMin, (long)head->val);
    max = (head->right == nullptr) ? head->val : std::max(rightMax, (long)head->val);
}

15. 修剪搜索二叉树

思路：
- 如果当前节点小于下界，则其左子树全部被修剪，返回右子树结果；
- 若大于上界，则返回左子树结果；
- 否则递归修剪左右子树。

题解：

// 修剪搜索二叉树
// 测试链接 : https://leetcode.cn/problems/trim-a-binary-search-tree/
TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (root == nullptr) {
        return nullptr;
    }
    if (root->val < low) {
        return trimBST(root->right, low, high);
    }
    if (root->val > high) {
        return trimBST(root->left, low, high);
    }
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
}

16. 二叉树打家劫舍问题

思路：
- 对每个节点，有两种状态：偷或不偷。
- 如果偷当前节点，则左右子节点不能偷；
- 如果不偷当前节点，则左右子节点自由选择，取最大收益；
- 最终返回两种状态中的最大值。

题解：

// 二叉树打家劫舍问题
// 测试链接 : https://leetcode.cn/problems/house-robber-iii/
int rob(TreeNode* root) {
    int isRob;
    int notRob;
    robHelper(root, isRob, notRob);
    return max(isRob, notRob);
}
void robHelper(TreeNode* root, int& isRob, int& notRob) {
    if (root == nullptr) {
        isRob = notRob = 0;
    } else {
        int isRobCur = root->val;
        int notRobCur = 0;
        // 左子树
        robHelper(root->left, isRob, notRob);
        isRobCur += notRob;
        notRobCur += max(isRob, notRob);
        // 右子树
        robHelper(root->right, isRob, notRob);
        isRobCur += notRob;
        notRobCur += max(isRob, notRob);
        isRob = isRobCur;
        notRob = notRobCur;
    }
}

数据结构题单

1. 最大频率栈

思路：
- 为每个数字记录出现频率（用哈希表 valueTimes）。
- 另用哈希表 cntValues，将相同频率的数字存入一个 vector 中，便于按栈的顺序访问。
- 维护一个 topTimes 变量表示当前的最大频率，push 时更新频率和对应的 vector，pop 时从最高频率的 vector 中取出栈顶数字，并在必要时减少 topTimes。

题解：

// 最大频率栈
// 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/
class FreqStack {
private:
    int topTimes;
    unordered_map<int, vector<int>> cntValues; // 频率 -> 对应的数字集合（按 push 顺序）
    unordered_map<int, int> valueTimes;          // 数字 -> 当前出现频率
public:
    FreqStack() {
        topTimes = 0;
    }
    ~FreqStack() { }
    void push(int val) {
        int curTopTimes = ++valueTimes[val];
        if (cntValues.find(curTopTimes) == cntValues.end()) {
            cntValues[curTopTimes] = vector<int>(); // 新建频率桶
        }
        cntValues[curTopTimes].push_back(val);
        topTimes = max(topTimes, curTopTimes);
    }
    
    int pop() {
        int ans = cntValues[topTimes].back();
        cntValues[topTimes].pop_back();
        if (cntValues[topTimes].empty()) {
            cntValues.erase(topTimes);
            topTimes--;
        }
        // 更新 valueTimes：如果频率为1则删除，否则减 1
        if (valueTimes[ans] == 1)
            valueTimes.erase(ans);
        else
            --valueTimes[ans];
        return ans;
    }
};

2. 实现 LRU 结构

思路：
- 使用双向链表维护数据的顺序，链表尾部为最新使用的节点，头部为最久未使用的节点。
- 结合哈希表 node_map，将 key 映射到对应的双向链表节点，便于快速查找。
- get 操作将节点移动到链表尾部；put 操作若 key 存在则更新并移动到尾部，否则若容量已满，则删除头节点，再插入新节点到尾部。

题解：

// 实现LRU结构
// 测试链接 : https://leetcode.cn/problems/lru-cache/
class LRUCache {
private:
    struct double_node {
        int key;
        int val;
        double_node* last;
        double_node* next;
        double_node(int k, int v) : key(k), val(v), last(nullptr), next(nullptr) {}
    };
    struct double_list {
        double_node* head;
        double_node* tail;
        double_list() : head(nullptr), tail(nullptr) {}
        void add_node(double_node* new_node) {
            if (new_node == nullptr) return;
            if (head == nullptr) {
                head = tail = new_node;
            } else {
                tail->next = new_node;
                new_node->last = tail;
                tail = new_node;
            }
        }
        void move_node2tail(double_node* node) {
            if (tail == node) return;
            if (head == node) {
                head = node->next;
                head->last = nullptr;
            } else {
                node->last->next = node->next;
                node->next->last = node->last;
            }
            node->last = tail;
            node->next = nullptr;
            tail->next = node;
            tail = node;
        }
        double_node* remove_head() {
            if (head == nullptr) return nullptr;
            double_node* ans = head;
            if (head == tail) {
                head = tail = nullptr;
            } else {
                head = ans->next;
                ans->next = nullptr;
                head->last = nullptr;
            }
            return ans;
        }
    };
    int capacity;
    double_list* node_list;
    unordered_map<int, double_node*> node_map;
public:
    LRUCache(int cap) {
        capacity = cap;
        node_list = new double_list();
    }
    
    ~LRUCache() {
        while (node_list->head) {
            double_node* temp = node_list->head;
            node_list->head = node_list->head->next;
            delete temp;
        }
        delete node_list;
    }
    
    int get(int key) {
        if (node_map.find(key) != node_map.end()) {
            double_node* node = node_map[key];
            node_list->move_node2tail(node);
            return node->val;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (node_map.find(key) != node_map.end()) {
            double_node* node = node_map[key];
            node->val = value;
            node_list->move_node2tail(node);
        } else {
            if (node_map.size() == capacity) {
                double_node* removed = node_list->remove_head();
                node_map.erase(removed->key);
                delete removed;
            }
            double_node* new_node = new double_node(key, value);
            node_map[key] = new_node;
            node_list->add_node(new_node);
        }
    }
};

3. 插入、删除和获取随机元素 O(1) 时间且允许重复

思路：
- 用 vector 存储所有元素，便于随机访问。
- 用哈希表 map 将每个值映射到其在 vector 中所有出现位置的 unordered_set。
- 插入时更新 vector 与 map；删除时将目标元素与 vector 最后一个元素交换，更新对应下标后 pop_back；获取随机数直接对 vector 随机下标取值。

题解：

// 插入、删除和获取随机元素O(1)时间且允许有重复数字的结构
// 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/
class RandomizedCollection {
private:
    unordered_map<int, unordered_set<int>> map; // 值 -> 下标集合
    vector<int> v; // 存储所有值
public:
    RandomizedCollection() { }
    ~RandomizedCollection() { }
    
    bool insert(int val) {
        v.push_back(val);
        map[val].insert(v.size() - 1);
        return map[val].size() == 1;
    }
    
    bool remove(int val) {
        if (map.find(val) == map.end()) {
            return false;
        }
        unordered_set<int>& valSet = map[val];
        int valAnyIndex = *valSet.begin();
        int endValue = v.back();
        if (val == endValue) {
            valSet.erase(v.size() - 1);
        } else {
            unordered_set<int>& endValueSet = map[endValue];
            endValueSet.insert(valAnyIndex);
            v[valAnyIndex] = endValue;
            endValueSet.erase(v.size() - 1);
            valSet.erase(valAnyIndex);
        }
        v.pop_back();
        if (valSet.empty()) {
            map.erase(val);
        }
        return true;
    }
    
    int getRandom() {
        int randIndex = rand() % v.size();
        return v[randIndex];
    }
};

4. 插入、删除和获取随机元素 O(1) 时间的结构

思路：
- 同样使用 vector 存储元素，哈希表记录每个值在 vector 中的索引。
- 插入时若元素已存在返回 false，否则插入并记录下标；删除时用最后一个元素覆盖待删除位置，并更新哈希表；随机取值直接从 vector 中获取。

题解：

// 插入、删除和获取随机元素O(1)时间的结构
// 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/
class RandomizedSet {
private:
    unordered_map<int, int> map; // 值 -> 索引
    vector<int> v;               // 存储所有值
public:
    RandomizedSet() { }
    ~RandomizedSet() { }
    
    bool insert(int val) {
        if (map.find(val) != map.end()) {
            return false;
        }
        map[val] = v.size();
        v.push_back(val);
        return true;
    }
    
    bool remove(int val) {
        if (map.find(val) == map.end()) {
            return false;
        }
        int valIndex = map[val];
        int lastValue = v.back();
        v[valIndex] = lastValue;
        map[lastValue] = valIndex;
        v.pop_back();
        map.erase(val);
        return true;
    }
    
    int getRandom() {
        if (v.empty()) return -1;
        int randomIndex = rand() % v.size();
        return v[randomIndex];
    }
};

5. 快速获得数据流中位数的结构

思路：
- 使用两个堆维护数据流：大顶堆 maxHeap 存较小一半数值，小顶堆 minHeap 存较大一半数值。
- 每次添加数据后通过平衡函数调整两个堆的大小差不超过 1，最终根据堆大小返回中位数（相等时取平均，不等时取较大堆的堆顶）。

题解：

// 快速获得数据流的中位数的结构
// 测试链接 : https://leetcode.cn/problems/find-median-from-data-stream/
class MedianFinder {
private:
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    void balance() {
        if (abs((int)(maxHeap.size() - minHeap.size())) == 2) {
            if (maxHeap.size() > minHeap.size()) {
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            } else {
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }
        }
    }
public:
    MedianFinder() { }
    ~MedianFinder() { }
    void addNum(int num) {
        if (maxHeap.empty() || maxHeap.top() >= num) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }
        balance();
    }
    
    double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (double)(maxHeap.top() + minHeap.top()) / 2.0;
        } else if (maxHeap.size() > minHeap.size()) {
            return (double)maxHeap.top();
        } else {
            return (double)minHeap.top();
        }
    }
};

6. 全 O(1) 的数据结构

思路：
- 采用双向链表维护桶（Bucket），每个桶存储相同计数的 key 集合。
- 用哨兵节点 head 和 tail 分别表示计数最小和最大的边界，利用哈希表 mp 将 key 映射到对应桶。
- inc 操作：若 key 不存在，则加入计数为 1 的桶；若存在，则移动到计数+1 的桶，并在当前桶空时删除。
- dec 操作：将 key 从当前桶移除，若计数减为 0 则删除 key，否则将其移到计数-1 的桶；同样在桶空时删除。
- getMaxKey 和 getMinKey 分别返回链表尾部和头部哨兵相邻桶中任意一个 key。

题解：

// 全O(1)的数据结构
// 测试链接 : https://leetcode.cn/problems/all-oone-data-structure/
class AllOne {
private:
    // 双向链表节点，存放“计数为 cnt 的所有 key”
    struct Bucket {
        int cnt;
        unordered_set<string> keys;  // 与该计数对应的所有 key
        Bucket* prev;
        Bucket* next;
        Bucket(int c) : cnt(c), prev(nullptr), next(nullptr) {}
    };

    // 头尾哨兵节点，不存任何有效 key，仅作占位
    Bucket* head;
    Bucket* tail;

    // map[key] => 指向该 key 所在的 Bucket
    unordered_map<string, Bucket*> mp;

    // 辅助函数：在 bucket 后插入新节点 newBucket
    void insertBucketAfter(Bucket* bucket, Bucket* newBucket) {
        newBucket->next = bucket->next;
        newBucket->prev = bucket;
        bucket->next->prev = newBucket;
        bucket->next = newBucket;
    }

    // 辅助函数：删除节点 bucket
    void removeBucket(Bucket* bucket) {
        bucket->prev->next = bucket->next;
        bucket->next->prev = bucket->prev;
        delete bucket;
    }

public:
    AllOne() {
        head = new Bucket(0);   // head哨兵
        tail = new Bucket(0);   // tail哨兵
        head->next = tail;
        tail->prev = head;
    }

    ~AllOne() {
        Bucket* cur = head;
        while (cur) {
            Bucket* nxt = cur->next;
            delete cur;
            cur = nxt;
        }
    }

    // key的计数+1
    void inc(const string &key) {
        if (mp.find(key) == mp.end()) {
            if (head->next != tail && head->next->cnt == 1) {
                head->next->keys.insert(key);
                mp[key] = head->next;
            } else {
                Bucket* newBucket = new Bucket(1);
                newBucket->keys.insert(key);
                insertBucketAfter(head, newBucket);
                mp[key] = newBucket;
            }
        } else {
            Bucket* curBucket = mp[key];
            int newCnt = curBucket->cnt + 1;
            curBucket->keys.erase(key);
            if (curBucket->next != tail && curBucket->next->cnt == newCnt) {
                curBucket->next->keys.insert(key);
                mp[key] = curBucket->next;
            } else {
                Bucket* newBucket = new Bucket(newCnt);
                newBucket->keys.insert(key);
                insertBucketAfter(curBucket, newBucket);
                mp[key] = newBucket;
            }
            if (curBucket->keys.empty()) {
                removeBucket(curBucket);
            }
        }
    }

    // key的计数-1
    void dec(const string &key) {
        Bucket* curBucket = mp[key];
        int newCnt = curBucket->cnt - 1;
        curBucket->keys.erase(key);
        if (newCnt == 0) {
            mp.erase(key);
        } else {
            if (curBucket->prev != head && curBucket->prev->cnt == newCnt) {
                curBucket->prev->keys.insert(key);
                mp[key] = curBucket->prev;
            } else {
                Bucket* newBucket = new Bucket(newCnt);
                newBucket->keys.insert(key);
                newBucket->next = curBucket;
                newBucket->prev = curBucket->prev;
                curBucket->prev->next = newBucket;
                curBucket->prev = newBucket;
                mp[key] = newBucket;
            }
        }
        if (curBucket->keys.empty()) {
            removeBucket(curBucket);
        }
    }

    // 返回出现次数最多的任意一个 key
    string getMaxKey() {
        if (tail->prev == head) return "";
        return *(tail->prev->keys.begin());
    }

    // 返回出现次数最少的任意一个 key
    string getMinKey() {
        if (head->next == tail) return "";
        return *(head->next->keys.begin());
    }
};