LeetCode 热题 100-能不能吃完饭再说

49、字母异位词分组——哈希表、排序

将异位词进行排序后可以得到相同字符串。遍历字符串数组，对每个字符串排序之后存入哈希表，最后将哈希表转化成数组即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        int cnt=0;
        for(auto str : strs){
            sort(str.begin(), str.end());
            map[str].emplace_back(strs[cnt]);
            cnt++;
        }
        vector<vector<string>> ret;
        for(auto pair : map){
            ret.emplace_back(pair.second);
        }
        return ret;
    }
};

128、最长连续序列和——哈希表、并查集

首先把数组排序，然后对数组进行遍历，记录当前序列的第一个元素set和最后一个元素pre：当遍历到的数字等于pre+1即可以组成序列时，则放入序列并尝试更新max；当数字等于pre，序列不一定在此中断，直接continue，尝试判断后续数字是否符合序列；若非以上两种情况的话，则说明一定被中断，直接设定新的set与pre。

最后返回记录的max中的第一个元素表示最长连续序列长度。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }
        sort(nums.begin(), nums.end());
        // 存储最大值和最大序列开头数字
        int max[2] = {1, 0};
        // 用于比较是否线性+1
        int pre = nums[0];
        // 当前序列的开头数字
        int set = nums[0];
        // 计数器
        int cnt = 1;
        unordered_map<int, vector<int>> map;
        map[set].emplace_back(set);
        for(int i=1;i<nums.size();i++){
            // 如果符合序列，则放入该集合
            if(nums[i]-1 == pre){
                map[set].emplace_back(nums[i]);
                pre++;
                cnt++;
                if(cnt>max[0]){
                    max[0] = cnt;
                    max[1] = set;
                }
            // 如果与pre相等，但是序列不一定被中断，后面的元素可能符合
            }else if(nums[i] == pre){
                continue;
            }
            // 完全被中断，直接重开
            else{
                cnt=1;
                set=nums[i];
                pre=set;
                map[set].emplace_back(set);
            }
        }
        return max[0];
    }
};

283、移动零——双指针

暴力方法，很简单，但是事件复杂度很高。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cnt = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                if(nums.size()-i == cnt){
                    break;
                }
                cnt++;
                int ptr = i;
                i--;
                for(int j=ptr+1;j<nums.size();j++){
                    int tmp = nums[j];
                    nums[j] = nums[ptr];
                    nums[ptr] = tmp;
                    ptr++;
                }
            }
        }
    }
};

优化

使用双指针，左指针指向当前已经处理好的序列的尾部（要么等于右指针要么指向0），右指针指向待处理序列的头部。右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。所以就是将右指针找到的非零数与处理好的序列的尾部0交换。注意到以下性质：

1、左指针左边均为非零数；

2、右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。动画表示如下

——————————————————————————————————

作者：力扣官方题解链接：https://leetcode.cn/problems/move-zeroes/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

15、三数之和——哈希表、排序、双指针

暴力方法

先排序。然后两层遍历，最后找到哈希表中是否有0-nums[i]-nums[j]这个元素，如果有则组成一对。这种方法好理解，但是性能很差，时间复杂度为O(n^2logn)。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<int, int> map;
        int len = nums.size();
        sort(nums.begin(), nums.end());
        for(int i=0;i<nums.size();i++){
            map[nums[i]] = i;
        }
        vector<vector<int>> ret;
        int cnt=0;
        int i = 0;
        int pre1;
        int pre2;
        do{
            pre1 = nums[i];
            int j=i+1;
            if(j == len){
                break;
            }
            do{
                pre2=nums[j];
                if(map.find(0-nums[i]-nums[j])!=map.end()){
                    int k = map[0-nums[i]-nums[j]];
                    if(k > j){
                        ret.push_back({nums[i], nums[j], nums[k]});
                        cnt++;
                    }
                }
                while(j<len && nums[j] == pre2){
                    j++;
                }
            }while(j<len);
            while(i<len && nums[i] == pre1){
                i++;
            }
        }while(i<len);
        return ret;
    }
};

双指针

优化后的时间复杂度为O(n^2)。首先进行排序，在第一层循环中，使用双指针来寻找符合条件的另外两个数字。

左指针指向i+1，右指针指向最后一个元素，当两个数字和小于target时，由于数组已被排序，则向右移动左指针，如果大于target，则向左移动右指针，如果相等则将这个组合放入结果。要注意避免获取重复的组合。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;  // 避免重复的组合
            }
            
            int target = -nums[i];
            int left = i + 1;
            int right = n - 1;
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;  // 避免重复的组合
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;  // 避免重复的组合
                    }
                }
            }
        }
        
        return ret;
    }
};

20、有效的括号——栈

栈。

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, int> cps;
        cps['{']=-1;
        cps['}']=1;
        cps['[']=-2;
        cps[']']=2;
        cps['(']=-3;
        cps[')']=3;
        char tmp;
        stack<char> chs;
        for(auto ch:s){
            if(chs.empty()){
                chs.push(ch);
            }else{
                tmp = chs.top();
                if(cps[tmp]+cps[ch]==0 && cps[tmp] < cps[ch]){
                    chs.pop();
                }else{
                    chs.push(ch);
                }
            }
        }
        return chs.empty();
    }
};

3、无重复字符的最长子串——滑动窗口、哈希表

自己写的又臭又烂的代码

两个指针，以一个指针为基指针，另一个指针向后移动，每次移动当移动到的元素不在哈希表中时，则放入哈希表并更新当前窗口大小和最大窗口大小，如果移动到的元素存在哈希表中，则说明这个无重复字符的子串到头了，将基指针移动到重复元素（左边那个）+1的位置继续移动窗口。直到另一个指针移动到了最后一个元素，返回结果。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(!s.size()){
            return 0;
        }
        int ret = 1;
        int left=0, right=0;
        for(;left<s.size();){
            int cnt = 1;
            unordered_map<char, int> exist;
            exist[s[left]] = left;
            right = left+1;
            if(right == s.size()){
                break;
            }
            while(exist.find(s[right])==exist.end()){
                exist[s[right]] = right;
                cnt++;
                right++;
                if(right == s.size()){
                    ret = max(ret, cnt);
                    return ret;
                }
            }
            if(right == s.size()){
                ret = max(ret, cnt);
                return ret;
            }
            left = exist[s[right]]+1;
            ret = max(ret, cnt);
        }
        return ret;
    }
};

GPT的优雅代码

在循环中，首先判断当前右指针指向的字符是否在窗口内。如果不在窗口内，则将该字符加入窗口，更新结果 ret 为当前窗口长度的最大值，然后右指针向右移动一位。如果当前右指针指向的字符已经在窗口内，则需要收缩窗口。将左指针指向的字符从窗口中移除，然后左指针向右移动直到到达那个重复的元素位置。

使用unordered_set 来存储窗口内的字符，上面的代码使用了 unordered_map。在查找元素的过程中，unordered_set 的查找时间复杂度是 O(1)，而 unordered_map 的查找时间复杂度也是 O(1)，但是由于 unordered_map 需要额外存储键和值的对应关系，会引入一些额外的开销，导致性能上的差异。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if (n == 0) {
            return 0;
        }

        unordered_set<char> window;
        int left = 0, right = 0;
        int ret = 0;

        while (left < n && right < n) {
            if (window.find(s[right]) == window.end()) {
                window.insert(s[right]);
                ret = max(ret, right - left + 1);
                right++;
            } else {
                window.erase(s[left]);
                left++;
            }
        }

        return ret;
    }
};

438、找到字符串中所有字母异位词——滑动窗口

初始化两个哈希表 pchs 和 schs，用于存储字符串 p 中每个字符的出现次数和滑动窗口中当前字符的出现次数。遍历字符串 p，将字符及其出现次数存储到 pchs 哈希表中。使用双指针 left 和 right 表示滑动窗口的左右边界，初始时都指向字符串的第一个位置。

如果字符 ch 在 pchs 哈希表中存在（即为字符串 p 中的字符），则将 schs 哈希表中对应字符的出现次数加1，然后将右指针 right 向右移动一位。如果滑动窗口的长度超过了字符串 p 的长度，即 right - left > plen，则需要将左指针 left 向右移动一位，并更新 schs 哈希表中相应字符的出现次数。如果某个字符的出现次数减少到0，就从 schs 哈希表中移除该键。当滑动窗口的长度等于字符串 p 的长度时，检查 schs 哈希表是否与 pchs 哈希表相等。如果相等，说明当前滑动窗口是一个字母异位词，将左指针 left 存入结果数组 ret 中。如果字符 ch 不在 pchs 哈希表中，表示当前字符不属于字符串 p 的字符，需要重置左指针 left 和右指针 right，并清空 schs 哈希表。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int left = 0, right = 0;
        unordered_map<char, int> pchs;
        unordered_map<char, int> schs;
        vector<int> ret;
        int len = s.size();
        int plen = p.size();

        // 初始化 pchs 哈希表
        for (auto ch : p) {
            pchs[ch]++;
        }

        while (right < len) {
            // 右指针移动并更新 schs 哈希表
            char ch = s[right];
            if (pchs.find(ch) != pchs.end()) {
                schs[ch]++;
                right++;

                // 当滑动窗口长度超过 p 的长度时，左指针移动并更新 schs 哈希表
                if (right - left > plen) {
                    char leftCh = s[left];
                    schs[leftCh]--;
                    if (schs[leftCh] == 0) {
                        schs.erase(leftCh);
                    }
                    left++;
                }

                // 当滑动窗口长度等于 p 的长度时，检查 schs 哈希表与 pchs 哈希表是否相等
                if (right - left == plen && schs == pchs) {
                    ret.push_back(left);
                }
            } else {
                // 当遇到不在 pchs 哈希表中的字符时，重置左指针和右指针，并清空 schs 哈希表
                left = right + 1;
                right = left;
                schs.clear();
            }
        }
        return ret;
    }
};

56、合并区间——排序

先对数组排序，比较函数使用 lambda 表达式来定义，它接受两个 vector<int> 类型的参数 a 和 b，分别表示两个区间，按照第一个元素升序排序，如果第一个元素相同，则按照第二个元素升序排序。

然后将第一个区间放入ret数组中。遍历 intervals 的区间作为a，并用一个cnt指向ret数组当前的区间b，判断a是否可以和b合并，如果可以合并则更新ret数组当前的区间的最大值，如果不可以则将该区间放入ret中，并将cnt+1继续寻找可以合并到cnt+1指向的区间。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ret;
        // 按照第一个元素进行升序排序，第一个元素相同则按照第二个元素升序排序
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) {
            return a[1] < b[1];
        }
            return a[0] < b[0];
        });
        // 将第一个区间放入
        int cnt=0;
        ret.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            // 如果新的区间可以与ret当前的区间合并
            if(intervals[i][0] <= ret[cnt][1]){
                ret[cnt][1] = max(intervals[i][1], ret[cnt][1]);
            }else{
                // 不能合并
                cnt++;
                ret.push_back(intervals[i]);
            }
        }
        return ret;
    }
};

记录：C++11引入了Lambda表达式作为一种语言特性，允许在C++中使用函数式编程的概念。Lambda表达式可以在需要函数对象的地方定义匿名函数，提供了一种简洁的方式来编写内联函数。官方文档C++ 中的 Lambda 表达式

各部分的含义如下：

capture列表：指定Lambda表达式的捕获列表，用于在Lambda表达式内部访问外部变量。可以通过值捕获、引用捕获或混合捕获的方式捕获变量。
参数列表：指定Lambda表达式的参数列表，与普通函数的参数列表类似。
mutable（可选）：指定Lambda表达式是否可以修改捕获的变量，默认情况下，Lambda表达式是不可变的。
异常属性（可选）：指定Lambda表达式抛出异常的属性。
返回类型（可选）：指定Lambda表达式的返回类型，可以根据上下文自动推断出返回类型，也可以显式指定返回类型。
函数体：指定Lambda表达式的实际代码逻辑。

[capture列表] (参数列表) mutable(可选) 异常属性(可选) -> 返回类型(可选) 
{ 
函数体 
}

简单示例

#include <algorithm>
#include <cmath>

void abssort(float* x, unsigned n) {
    std::sort(x, x + n,
        // Lambda expression begins
        [](float a, float b) {
            return (std::abs(a) < std::abs(b));
        } // end of lambda expression
    );
}

图片[2]-LeetCode 热题 100-能不能吃完饭再说

560、和为K的子数组——哈希表、前缀和

走了一点弯路

先把所有前缀和计算，然后存在哈希表中，值为一个数组，表示以此键为前缀和的元素下标数组。

然后开始遍历哈希表，以当前前缀和为右界的前缀和，如果哈希表种存在一个前缀和比该前缀和小k，则说明可能存在和为k的子数组。

然后遍历右界的下标数组，在其中遍历左界的下标数组，如果存在right大于left的情况，则存在一个和为k的子数组

虽然可以过，但是时间复杂度和空间复杂度都很烂🥲

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        int ret = 0;
        unordered_map<int, vector<int>> pre;
        int tmppre = 0;
        pre[tmppre].push_back(0);
        for(int i=0;i<len;i++){
            pre[tmppre+nums[i]].push_back(i+1);
            tmppre += nums[i];
        }
        for(auto& pair:pre){
            if(pre.find(pair.first-k) != pre.end()){
                for(auto& right:pair.second){
                    for(auto& left:pre[pair.first-k]){
                        if(right > left){
                            ret++;
                        }
                    }
                }
            }
        }
        return ret;
    }
};

优化

上面的代码，我们遍历左右界下标数组来判断是否存在right大于left的情况。但是转念一想，我们好像可以在遍历nums数组建立前缀和表的时候存储前缀和的次数，在计算前缀和的过程中统计和为K的子数组数量。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        int ret = 0;
        unordered_map<int, int> pre;
        int tmppre = 0;
        pre[tmppre] = 1;
        for(int i=0;i<len;i++){
            tmppre += nums[i];
            if(pre.find(tmppre-k)!=pre.end()){
                ret += pre[tmppre-k];
            }
            pre[tmppre]++;
        }
        return ret;
    }
};

94、二叉树的中序遍历——二叉树

中序遍历，简单题不说了🤤

/**
 * 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 in(TreeNode* node){
        if(node == nullptr){
            return;
        }
        in(node->left);
        inorder.push_back(node->val);
        in(node->right);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        in(root);
        return inorder;
    }
private:
    vector<int> inorder;
};

189、轮转数组——队列

暴力方法

开辟一个新的空间，存储原来的数组状态，然后进行旋转。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        queue<int> q;
        int len = nums.size();
        for(auto& num:nums){
            q.push(num);
        }
        for(int i=0;i<len;i++){
            int num = q.front();
            q.pop();
            nums[(i+k)%len]  = num;
        }   
    }
};

优化

实际上可以在原本的空间进行操作。

将轮转数组整个过程简化描述，其实就是将最后k个元素移动到前面。简化操作就是先将整个数组反转，然后再单独反转前k个元素和剩余所有元素就能实现将最后k个元素移动到前面。

比如对于[5, 6, 7, 1, 2, 3, 4]，k=3。反转整个向量：[7, 6, 5, 4, 3, 2, 1]，反转前 k 个元素：[5, 6, 7, 4, 3, 2, 1]，反转剩余的 len – k 个元素：[5, 6, 7, 1, 2, 3, 4]。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        k = k % len; // 处理 k 大于 nums 长度的情况

        reverse(nums, 0, len - 1); // 先反转整个向量
        reverse(nums, 0, k - 1); // 再反转前 k 个元素
        reverse(nums, k, len - 1); // 最后反转剩余的元素
    }

private:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start++;
            end--;
        }
    }
};

238、除自身以外数组的乘积——前缀积、后缀积

要求不能用除法，同时时间复杂度为O(n)。

除自身以外数组的乘积即该元素的前缀积与后缀积的乘积，因此先建立前缀积数组。然后从尾部开始遍历数组，并用tmp保存当前元素后缀积。然后计算前缀与后缀的积并放入answer数组。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> pre;
        int len = nums.size();
        vector<int> answer(len, 0);
        int tmp = 1;
        pre.push_back(1);
        for(int i = 0;i < len;i++){
            tmp = nums[i]*tmp;
            pre.push_back(tmp);
        }
        tmp = 1;
        for(int i = len-1;i>=0;i--){
            answer[i] = pre[i]*tmp;
            tmp = nums[i]*tmp;
        }
        return answer;
    }
};

73、矩阵置零——哈希表

首先遍历整个矩阵，用哈希集合记录需要置零的行和列。然后分别将这些行列置零。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> cols;
        unordered_set<int> rows;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
                if(matrix[i][j] == 0){
                    rows.insert(i);
                    cols.insert(j);
                }
            }
        }
        for(auto& row:rows){
            for(int i=0;i<matrix[row].size();i++){
                matrix[row][i] = 0;
            }
        }
        for(auto& col:cols){
            for(int i=0;i<matrix.size();i++){
                matrix[i][col] = 0;
            }
        }
    }
};

54、螺旋矩阵——模拟

使用left、right、top、bottom存储遍历的上下左右边界，然后遍历四条边同时更新上下左右边界。注意在遍历过程中判断是否还有元素可以遍历，避免重复遍历元素。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        if(matrix.empty()){
            return ret;
        }
        int h = matrix.size();
        int w = matrix[0].size();
        int left=0, right=w-1, top=0, bottom=h-1;
        while(left <= right && top <= bottom){
            for(int i=left;i<=right;i++){
                ret.push_back(matrix[top][i]);
            }
            top++;
            for(int i=top;i<=bottom;i++){
                ret.push_back(matrix[i][right]);
            }
            right--;
            if(top <= bottom){
                for(int i=right;i>=left;i--){
                    ret.push_back(matrix[bottom][i]);
                }
                bottom--;
            }
            if(left <= right){
                for(int i=bottom;i>=top;i--){
                    ret.push_back(matrix[i][left]);
                }
                left++;
            }
        }
        return ret;
    }
};

160、相交链表——哈希表

先遍历一个链表，并插入哈希集合。再遍历另一个链表，找到在哈希集合中的第一个元素并返回。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> nodes;
        ListNode *tmp = headA;
        nodes.insert(headA);
        while(tmp->next){
            nodes.insert(tmp->next);
            tmp = tmp->next;
        }
        tmp = headB;
        while (tmp) {
            if (nodes.find(tmp) != nodes.end()) {
                return tmp;
            }
            tmp = tmp->next;
        }
        return nullptr;
    }
};

48、旋转图像

相通了就很简单，一个矩阵旋转顺时针旋转90°，即先将矩阵转置在将每一行水平翻转即可。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // 对矩阵转置
        for(int i=0;i<matrix.size();i++){
            for(int j=i+1;j<matrix[i].size();j++){
                swap(matrix[i][j], matrix[j][i]);
            }
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

240、搜索二维矩阵Ⅱ——二分查找

第一次二分查找找到target可能存在的行的范围，第二次遍历这些行并使用二分法查找其中的target。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int len = matrix.size();
        int potential_row;
        int left = 0, right = len-1;
        while(left <= right){
            int mid = (left+right)/2;
            if(matrix[mid][0] > target){
                right = mid-1;
            }else if(matrix[mid][0] < target){
                left = mid+1;
            }else{
                return true;
            }
        }
        potential_row = left;
        len = matrix[0].size();
        for(int i=0;i<potential_row;i++){
            auto it = lower_bound(matrix[i].begin(), matrix[i].end(), target);
            if(it != matrix[i].end() && *it == target){
                return true;
            }
        }
        return false;
    }
};

234、回文链表——递归、双指针

双指针

先存储原链表的内容，然后递归反转链表，最后遍历新链表和原链表内容，判断是否为回文链表。

这里可以不用反转链表，直接从原链表内容的最后开始往前移动，但是不知道为什么这种方法比先反转时间更长。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* node) {
        if(node == nullptr || node->next == nullptr){
            return node;
        }
        ListNode* tmp = reverseList(node->next);
        node->next->next = node;
        node->next = nullptr;
        return tmp;
    }

    bool isPalindrome(ListNode* head) {
        ListNode* tmp = head;
        vector<int> raw_list;
        while(tmp != nullptr){
            raw_list.push_back(tmp->val);
            tmp = tmp->next;
        }
        head = reverseList(head);
        tmp = head;
        int cnt=0;
        while(tmp != nullptr){
            if(tmp->val != raw_list[cnt]){
                return false;
            }
            tmp = tmp->next;
            cnt++;
        }
        return true;
    }
};

递归

定义了一个辅助指针 frontPointer，用于记录链表的当前前向节点。然后，使用递归函数 recursivelyCheck() 来检查链表是否为回文。

1、如果当前节点不为空，首先递归调用 recursivelyCheck() 函数，传入当前节点的下一个节点，并检查返回值是否为 false。如果不是回文，则直接返回 false。

2、如果当前节点的值与 frontPointer 节点的值不相等，则返回 false。

3、将 frontPointer 指针指向下一个节点，以便继续与后续节点比较

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* frontPointer;
public:
    bool recursivelyCheck(ListNode* currentNode) {
        if (currentNode != nullptr) {
            if (!recursivelyCheck(currentNode->next)) {
                return false;
            }
            if (currentNode->val != frontPointer->val) {
                return false;
            }
            frontPointer = frontPointer->next;
        }
        return true;
    }

    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};

141、环形链表——哈希表

遍历链表，如果节点在哈希表中，则说明存在环，返回true，否则将指针插入哈希集合。最后如果没找到环返回false。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode *> vistited;
        ListNode *tmp = head;
        while(tmp != nullptr){
            if(vistited.find(tmp) != vistited.end()){
                return true;
            }
            vistited.insert(tmp);
            tmp = tmp->next;
        }
        return false;
    }
};

21、合并两个有序链表——链表、双指针

判断其中一个链表是否为空来处理特殊情况。如果list1为空，则直接返回list2；如果list2为空，则直接返回list1。

在每次循环中，通过比较list1和list2当前节点的值的大小，来确定下一个节点的指向。如果list1的当前节点值小于等于list2的当前节点值，那么将tmp的下一个节点指向list1的当前节点，并将list1指向下一个节点；否则，将tmp的下一个节点指向list2的当前节点，并将list2指向下一个节点。然后，更新tmp为其下一个节点。

在每次循环的末尾，检查list1和list2是否有一个已经遍历完（即为nullptr），如果有，则将tmp的下一个节点指向未遍历完的链表，然后退出循环。

最后，返回newHead的下一个节点，即为合并后的链表的头节点。时间复杂度为O(m+n)，其中m和n分别为两个链表的长度。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr){
            return list2;
        }else if(list2 == nullptr){
            return list1;
        }
        ListNode* newHead = new ListNode();
        ListNode* tmp = newHead;
        while(true){
            if(list1->val <= list2->val){
                tmp->next = list1;
                list1 = list1->next;
            }else{
                tmp->next = list2;
                list2 = list2->next;
            }
            tmp = tmp->next;
            if(list1 == nullptr){
                tmp->next = list2;
                break;
            }else if(list2 == nullptr){
                tmp->next = list1;
                break;
            }
        }
        return newHead->next;
    }
};

19、删除链表的第N个节点——双指针

两次扫描

两次遍历删除倒数第N个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* node = head;
        int cnt = 0;
        while(node!=nullptr){
            node = node->next;
            cnt++;
        }
        node = head->next;
        ListNode* pre = head;
        int cur=1;
        // 如果要删除第一个
        if(n == cnt){
            delete head;
            head = nullptr;
            return node;
        }
        while(node!=nullptr){
            if(cur == cnt-n){
                pre->next = node->next;
                delete node;
                node = nullptr;
                break;
            }
            pre = pre->next;
            node = node->next;
            cur++;
        }
        return head;
    }
};

一次扫描

先让fast指针移动n步，然后fast和last指针一起移动直到fast指针移动到末尾，那样last指针就指向要删除节点的前一节点了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        
        ListNode* fast = dummy;
        ListNode* slow = dummy;

        // 将 fast 指针向前移动 n 步
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }
        // 同时移动 fast 和 slow 指针，直到 fast 到达链表末尾
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* delnode = slow->next;
        slow->next = slow->next->next;
        ListNode* result = dummy->next;

        delete delnode;
        delete dummy;
        
        return result;
    }
};

24、两两交换链表中的节点——递归

函数首先检查当前节点的下一个节点是否为空，如果为空，则表示当前节点是链表的最后一个节点，无需进行交换，直接返回。接着，函数创建一个指针nx指向当前节点的下一个节点。然后，它检查nx的下一个节点是否为空，如果为空，则表示nx是链表的最后一个节点，即当前节点是倒数第二个节点，这是最后一对节点。在这种情况下，进行节点交换操作，将node的下一个节点指针指向nx的下一个节点，将nx的下一个节点指针指向node，完成节点交换。如果nx的下一个节点不为空，则说明还有至少两个节点需要交换。在这种情况下，函数根据节点的奇偶性来更新node的下一个节点指针，然后递归调用SwitchNode函数，传入nx的下一个节点作为参数。最后，将nx的下一个节点指针指向node，完成节点交换。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void SwitchNode(ListNode* node){
        if(node->next == nullptr){
            return;
        }
        ListNode* nx = node->next;
        if(nx->next == nullptr){
            node->next = nx->next;
            nx->next = node;
        }else{
            // 下一对为后偶数
            if(nx->next->next != nullptr){
                node->next = nx->next->next;
            }else{
                // 奇数
                node->next = nx->next;
            }
            SwitchNode(nx->next);
            nx->next = node;
        }
    }

    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr){
            return nullptr;
        }else if(head->next == nullptr){
            return head;
        }
        ListNode* ret = head->next;
        SwitchNode(head);
        return ret;
    }
};

148、排序链表——归并排序、递归、分治、双指针

首先，检查链表是否为空或只包含一个节点。如果是，直接返回原链表，因为它已经是有序的。使用快慢指针将链表分成两部分。快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表尾部时，慢指针指向链表的中间节点。然后递归调用对左右两个链表进行排序，排序后对左右两个链表进行归并排序。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 0节点或1节点，直接返回
        if(head==nullptr || head->next == nullptr){
            return head;
        }
        // 快慢节点
        ListNode* last = head;
        ListNode* fast = head->next;
        while(fast != nullptr && fast->next != nullptr){
            last = last->next;
            fast = fast->next->next;
        }
        // 将链表分为左右两个链表
        ListNode* rightHead = last->next;
        last->next = nullptr;
        // 对左右两个链表排序
        ListNode* sortLeft = sortList(head);
        ListNode* sortRight = sortList(rightHead);
        // 进行归并排序
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(sortLeft != nullptr && sortRight != nullptr){
            if(sortLeft->val <= sortRight->val){
                cur->next = sortLeft;
                sortLeft = sortLeft->next;
            }else{
                cur->next = sortRight;
                sortRight = sortRight->next;
            }
            cur = cur->next;
        }
        // 处理剩余节点
        if (sortLeft != nullptr) {
            cur->next = sortLeft;
        }
        if (sortRight != nullptr) {
            cur->next = sortRight;
        }
        return dummy->next;
    }
};

226、翻转二叉树——递归

首先简化问题，翻转一个二层的满二叉树，那么就是交换根节点的左右子节点，三层的满二叉树就是先对根节点的左右子节点进行对二层满二叉树的操作之后再交换左右子树，以此类推。

所以可以使用递归，首先检查根节点是否为空，如果为空，则直接返回 nullptr。如果根节点是叶节点（即左右子节点都为空），则直接返回根节点。然后递归调用函数翻转左右子树，再交换左右子树的位置。

/**
 * 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* invertTree(TreeNode* root) {
        // 根节点为空
        if(root == nullptr){
            return nullptr;
        // 为叶节点 
        }else if(root->left == nullptr && root->right == nullptr){
            return root;
        }
        // 分别翻转左右子树
        invertTree(root->left);
        invertTree(root->right);
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
    }
};

101、对称二叉树——递归

迭代

使用层序遍历的思想来逐层检查二叉树的对称性。使用队列 q 来进行层序遍历。将根节点入队。然后，定义一个变量 levelSize 来表示当前层的节点数，初始值为 1。定义了一个指向 nullptr 的指针 nullNode，用于表示空节点。

接下来，进入一个循环，直到队列为空。在每次循环中，创建一个空的 vector<int>，用于存储当前层的节点值。然后，遍历当前层的节点数，从队列中取出节点。如果当前节点为空，即为 nullptr，则将 INT_MIN 存入 level 中，并将两个空节点（nullNode）入队，表示当前节点的左右子节点为空。如果当前节点不为空，则将其值存入 level 中，并将其左右子节点入队。

在遍历完当前层的节点后，检查 level 是否对称。使用双指针的方式，从两端向中间遍历，如果发现值不相等，则二叉树不对称，直接返回 false。然后，检查当前层是否全为空节点，即所有节点的值都为 INT_MIN。如果是，则认为二叉树已经检查完毕，没有更多的层需要遍历，跳出循环。最后，将 levelSize 乘以 2，以准备遍历下一层。

不过是很蠢的办法😓

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        queue<TreeNode*> q;
        q.push(root);
        int levelSize = 1;
        TreeNode* nullNode = nullptr;
        while (!q.empty()) {
            vector<int> level(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode* current = q.front();
                q.pop();
                if(current == nullptr){
                    level[i] = INT_MIN;
                    q.push(nullNode);
                    q.push(nullNode);
                    continue;
                }
                level[i] = current->val;
                if (current->left != nullptr) {
                    q.push(current->left);
                }else{
                    q.push(nullNode);
                }
                if (current->right != nullptr) {
                    q.push(current->right);
                }else{
                    q.push(nullNode);
                }
            }
            bool q = true;
            for(int i = 0; i < (levelSize+1)/2; i++){
                if(level[i] != INT_MIN){
                    q=false;
                }
                if(level[i] != level[levelSize-i-1]){
                    return false;
                }
            }
            if(q){
                break;
            }
            levelSize *= 2;
        }
        return true;
    }
};

递归

isSymmetricHelper，该函数接受两个节点指针 left 和 right，用于递归判断左右子树的对称性。

在 isSymmetricHelper 函数内部，首先进行了两个节点的判空情况的判断。如果左节点和右节点均为空，说明当前层对称，返回 true。如果左节点或右节点有一个为空，说明当前层不对称，返回 false。接下来，比较左右节点的值是否相等。如果不相等，说明当前层不对称，返回 false。

递归调用 isSymmetricHelper 函数判断左节点的左子树和右节点的右子树是否对称，以及左节点的右子树和右节点的左子树是否对称。如果两个子树均对称，返回 true，否则返回 false。

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        return isSymmetricHelper(root->left, root->right);
    }

private:
    // 判断左右子树是否相等
    bool isSymmetricHelper(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) {
            return true;
        }
        if (left == nullptr || right == nullptr) {
            return false;
        }
        // 树的根节点相等
        // 左树的左子树与右树的右子树相等
        // 左树的右子树与右树的左子树相等
        return (left->val == right->val) &&
               isSymmetricHelper(left->left, right->right) &&
               isSymmetricHelper(left->right, right->left);
    }
};

142、环形链表Ⅱ——哈希表

遍历链表，如果节点在哈希表中，则说明存在环，返回该节点，否则将指针插入哈希集合。最后如果没找到环返回null。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> vistited;
        ListNode *tmp = head;
        while(tmp != nullptr){
            if(vistited.find(tmp) != vistited.end()){
                return tmp;
            }
            vistited.insert(tmp);
            tmp = tmp->next;
        }
        return nullptr;
    }
};

543、二叉树的直径——递归

deep 函数是一个递归函数，用于计算以当前节点为根节点的子树的深度，并更新直径的值。函数首先判断当前节点是否为空，如果为空则返回深度 0。然后判断当前节点是否为叶子节点，即左右子节点都为空，如果是则返回深度 1。如果当前节点不是叶子节点，则递归计算左子树和右子树的深度，并将左子树深度和右子树深度相加，与当前的最大直径进行比较，更新最大直径的值。最后，返回左子树深度和右子树深度中的较大值加 1，即当前根节点的子树的深度。

/**
 * 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:
    int deep(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        if(root->left == nullptr && root->right == nullptr){
            return 1;
        }
        int left = deep(root->left);
        int right = deep(root->right);
        max = left+right>max?left+right:max;
        int ret = left>right?left:right;
        return ret+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int ret = deep(root);
        return max;
    }
private:
    int max = 0;
};

102、二叉树的层序遍历——队列

创建一个队列 node_queue，并将根节点入队。

进入循环，判断队列是否为空。如果队列不为空，说明还有节点需要遍历。在每一轮循环中，首先获取当前层的节点数量 level_size，这是为了在每一层结束后创建一个新的层向量。

然后，创建一个一维向量 level，用于存储当前层的节点值。

接下来，通过循环遍历当前层的节点。在循环中，从队列中取出一个节点 cur，将其值存储到当前层的向量 level 的对应位置。然后，如果当前节点的左子节点不为空，将其左子节点入队。如果当前节点的右子节点不为空，将其右子节点入队。

完成当前层的遍历后，将存储当前层节点值的向量 level 插入结果向量 ret 中。

重复以上步骤，直到队列为空，即二叉树的所有节点都遍历完毕。

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr) {
            return ret;
        }
        queue<TreeNode*> node_queue;
        node_queue.push(root);
        while(!node_queue.empty()){
            int level_size = node_queue.size();
            vector<int> level(level_size);
            for(int i=0;i<level_size;i++){
                TreeNode* cur = node_queue.front();
                node_queue.pop();
                level[i] = cur->val;
                if(cur->left != nullptr){
                    node_queue.push(cur->left);
                }
                if(cur->right != nullptr){
                    node_queue.push(cur->right);
                }

            }
            ret.push_back(level);
        }
        return ret;
    }
};

138、随机链表的复制——哈希表、深拷贝

深拷贝与浅拷贝

使用了两个哈希映射，node_map和re_node_map，用于建立原始节点与复制节点之间的映射关系。在DeepCopy函数中，通过传入一个节点other，创建一个新的节点node，并将其值初始化为other节点的值。然后，将other节点和node节点作为键值对分别存储在node_map和re_node_map中，以便后续根据原始节点查找对应的复制节点。

遍历原始链表，对于每个节点cur，通过调用DeepCopy函数复制节点，并将复制节点连接到复制链表的末尾。同时，更新cur和tmp指针指向下一个节点。

接下来，再次遍历复制链表，对于每个复制节点tmp，根据re_node_map找到对应的原始节点，并根据random指针的映射关系，设置复制节点的random指针指向正确的节点。

最后，返回复制链表的头节点dummy->next。

/*
// 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* DeepCopy(Node* other){
        Node* node = new Node(other->val);
        node_map[other] = node;
        re_node_map[node] = other;
        return node;
    }
    Node* copyRandomList(Node* head) {
        Node* cur = head;
        Node* dummy = new Node(-1);
        Node* tmp = dummy;
        while(cur != nullptr){ 
            tmp->next = DeepCopy(cur);
            cur = cur->next;
            tmp = tmp->next;
        }
        tmp = dummy->next;
        while(tmp != nullptr){
            tmp->random = node_map[re_node_map[tmp]->random];
            tmp = tmp->next;
        }
        return dummy->next;
    }
private:
    unordered_map<Node*, Node*> node_map;
    unordered_map<Node*, Node*> re_node_map;
};

108、将有序数据转换为平衡二叉搜索树——递归、分治、AVL树

在 insertAVLTree 函数中，通过递归的方式，将有序数组分为左右两部分，并选取中间元素作为根节点，然后构建左子树和右子树。在构建过程中，调用 insertNode 函数插入节点到二叉搜索树中。

insertNode 函数用于将节点插入到二叉搜索树中的正确位置。它按照节点的值大小进行比较，如果节点的值比当前节点大，则进入右子树；如果节点的值比当前节点小，则进入左子树。直到找到合适的位置插入节点。

/**
 * 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 insertNode(TreeNode* node){
        TreeNode* cur = root;
        if(cur == nullptr){
            root = node;
            return;
        }
        while(true){
            if(node->val > cur->val){
                if(cur->right == nullptr){
                    cur->right = node;
                    return;
                }
                cur = cur->right;
            }else if(node->val < cur->val){
                if(cur->left == nullptr){
                    cur->left = node;
                    return;
                }
                cur = cur->left;
            }else{
                return;
            }
        }
    }

    void insertAVLTree(vector<int>& nums, int begin, int end){
        if(begin > end){
            return;
        }
        int mid = (begin + end)/2; 
        TreeNode* node = new TreeNode(nums[mid]);
        insertNode(node);
        if(begin == end){
            return;
        }
        insertAVLTree(nums, begin, mid-1);
        insertAVLTree(nums, mid+1, end);
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        insertAVLTree(nums, 0, nums.size() - 1);
        return root;
    }
private:
    TreeNode* root;
};

98、验证二叉搜索树——二叉树、中序遍历

中序遍历二叉树，然后判断是否为递增的有序数组。

/**
 * 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:
    vector<int> nums;
    void inorderTravel(TreeNode* root){
        if(root == nullptr){
            return;
        }
        inorderTravel(root->left);
        nums.push_back(root->val);
        inorderTravel(root->right);
    }
    bool isValidBST(TreeNode* root) {
        inorderTravel(root);
        for(int i=1;i<nums.size();i++){
            if(nums[i] <= nums[i-1]){
                return false;
            }
        }
        return true;
    }
};

230、二叉搜索树中第K小的元素——中序遍历

首先检查当前节点是否为空，如果为空则返回。然后它递归地调用自身来处理当前节点的左子树。接着，它增加计数器cnt的值，表示已经遍历过一个节点。如果计数器的值等于k，说明找到了第k个节点，将当前节点的值记录在变量find中。最后，getNum函数再递归地处理当前节点的右子树。

最后，kthSmallest函数返回变量find，即第k小的元素的值。

/**
 * 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:
    int cnt=0;
    int find;
    void getNum(TreeNode* root, int k){
        if(root == nullptr){
            return;
        }
        getNum(root->left, k);
        cnt++;
        if(cnt == k){
            find=root->val;
        }
        getNum(root->right, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        getNum(root, k);
        return find;
    }
};

------本页内容已结束，喜欢请分享------

文章作者

能不能吃完饭再说

隐私政策

PrivacyPolicy

用户协议

UseGenerator

许可协议

NC-SA 4.0

文章版权归作者所有，未经允许请勿转载。

THE END

LeetCode 热题 100

49、字母异位词分组——哈希表、排序

128、最长连续序列和——哈希表、并查集

283、移动零——双指针

优化

15、三数之和——哈希表、排序、双指针

暴力方法

双指针

20、有效的括号——栈

3、无重复字符的最长子串——滑动窗口、哈希表

自己写的又臭又烂的代码

GPT的优雅代码

438、找到字符串中所有字母异位词——滑动窗口

56、合并区间——排序

560、和为K的子数组——哈希表、前缀和

走了一点弯路

优化

94、二叉树的中序遍历——二叉树

189、轮转数组——队列

暴力方法

优化

238、除自身以外数组的乘积——前缀积、后缀积

73、矩阵置零——哈希表

54、螺旋矩阵——模拟

160、相交链表——哈希表

48、旋转图像

240、搜索二维矩阵Ⅱ——二分查找

234、回文链表——递归、双指针

双指针

递归

141、环形链表——哈希表

21、合并两个有序链表——链表、双指针

19、删除链表的第N个节点——双指针

两次扫描

一次扫描

24、两两交换链表中的节点——递归

148、排序链表——归并排序、递归、分治、双指针

226、翻转二叉树——递归

101、对称二叉树——递归

迭代

递归

142、环形链表Ⅱ——哈希表

543、二叉树的直径——递归

102、二叉树的层序遍历——队列

138、随机链表的复制——哈希表、深拷贝

108、将有序数据转换为平衡二叉搜索树——递归、分治、AVL树

98、验证二叉搜索树——二叉树、中序遍历

230、二叉搜索树中第K小的元素——中序遍历

1SQL注入基础教程

2Nachos文件系统调用与shell

3Adaline自适应线性神经元和学习收敛

4系统调用详解:以Nachos为例实现系统调用

5SeedLab——Environment Variable and Set-UID Program Lab

6机器学习入门-python实现感知器算法