Useful URL

代码随想录

灵茶山艾府：如何科学刷题 + 算法题单

Random Problem

哈希

1.两数之和

Leetcode 热题 100 —— 两数之和

m1.c++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        //暴力
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(nums[i] + nums[j] == target){
                    return {i, j};
                }
            }
        }
        return {0, 0};
    }
};

m2.c++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        // pair固定字节
        vector<pair<int, int>> res;
        for(int i = 0; i < n; i++){
            res.push_back({nums[i], i});
        }
        sort(res.begin(), res.end());

        int l = 0, r = n - 1;
        //双指针
        while(l < r){
            if(res[l].first + res[r].first == target){
                return {res[l].second, res[r].second};
            }else if(res[l].first + res[r].first < target){
                l++;
            }else{
                r--;
            }
        }
        return {0, 0};
    }
};

m3.c++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //Hash表
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++){
            int target_num = target - nums[i];
            if(mp.find(target_num) != 0){
                return {mp[target_num], i};
            }
            mp[nums[i]] = i;
        }
        return {0, 0};
    }
};

2.字母异位词分组

Leetcode 热题 100 —— 字母异位词分组

m1.c++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        vector<vector<string>> res;
        for(auto &s : strs){
            auto key = s;
            sort(key.begin(), key.end());
            mp[key].push_back(s);
        }


        for(auto &ele : mp){
            res.push_back(ele.second);
        }
        return res;
    }
};

3.最长连续序列

Leetcode 热题 100 —— 最长连续序列

m1.c++

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }

        int n = nums.size();
        auto arr = nums;
        sort(arr.begin(), arr.end());

        int len = 1, max_len = 1;
        for(int i = 1; i < n;i++){
            if(arr[i] == arr[i - 1]){
                continue;
            }
            if(arr[i] == arr[i - 1] + 1){
                len++;
            }else{
                max_len = max(max_len, len);
                len = 1;
            }
        }

        return max(max_len, len);
    }
};

m2.c++

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        unordered_set<int> st(nums.begin(), nums.end());

        int n = nums.size();
        int len, max_len = 1;
        for(auto &s : st){
            auto x = s;
            len = 1;
            if(st.count(x - 1) == 0){
                while(st.count(x + 1) != 0){
                    len++;
                    x++;
                }
            }
            max_len = max(max_len, len);
        }

        return max_len;
    }
};

双指针

1.移动零

Leetcode 热题 100 —— 移动零

m1.c++

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

        for(int i = j; i < nums.size(); i++){
            nums[i] = 0;
        }
    }
};

m2.c++

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j = 0;
        int n = nums.size();
        //冒泡排序思路
        for(int i = 0; i < n; i++){
            if(nums[i] != 0){
                //每一个非0元素都会以相对的顺序进入到j++的索引中
                swap(nums[j++], nums[i]);
            }
        }
    }
};

2.盛最多水的容器

Leetcode 热题 100 —— 盛最多水的容器

m1.c++

/**
木桶效应，相比之下，较短的那一个木板向中间收敛
如果短的不向中聚拢，那么就是长的向中聚拢，会造成结果：v只会越来越小
*/
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int v = 0;
        int l = 0, r = n - 1;
        while(l < r){
            v = max(v, min(height[l], height[r]) * (r - l));
            if(height[l] < height[r]){
                l++;
            }else{
                r--;
            }
        }
        return v;
    }
};

3.三数之和

Leetcode 热题 100 —— 三数之和

m1.c++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        // 双指针在有序的时候才能发挥作用
        sort(nums.begin(), nums.end());

        vector<vector<int>> res;
        //n - 3, n - 2, n - 1
        for(int i = 0; i < n - 2; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = n - 1;
            while(l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == 0){
                    res.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                    /**
                     l: 0 [1](l - 1) [1](l)  2(r)  2(r + 1)
                     同上，去重，双指针拥有天然去重的优势
                    */
                    while(l < r && nums[l] == nums[l - 1]) l++;
                    while(l < r && nums[r] == nums[r + 1]) r--;
                }else if(sum < 0){
                    l++;
                }else{
                    r--;
                }
            }
        }

        return res;
    }
};

m2.c++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        for(int i = 0; i < n; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            // nums[i]; target_num = - nums[i];
            unordered_map<int, int> mp;
            for(int j = i + 1; j < n; j++){
                int target_num = -nums[i] - nums[j];
                if(mp.find(target_num) != 0 && i != j && i != mp[target_num] && j != mp[target_num]){
                    vector<int> v = {nums[i], nums[j], target_num};
                    sort(v.begin(), v.end());
                    res.push_back(v);
                }
                mp[nums[j]] = j;
            }
        }

        sort(res.begin(), res.end());
        res.erase(unique(res.begin(), res.end()), res.end());
        return res;
    }
};

4.接雨水

Leetcode 热题 100 —— 接雨水

m1.c++

class Solution {
public:
    int trap(vector<int>& height) {
        /**
        固定一个柱子，利用dp找到自身，左右两侧最高的柱子，
        "min(左侧最高的柱子，右侧最高的柱子) - 自身height"就是自己可以承受最多的水
        */
        int n = height.size();
        vector<int> l(n), r(n), res(n);

        //l[i] = max(l[i - 1], height[i])
        l[0] = 0;
        for(int i = 1; i < n; i++){
            l[i] = max(l[i - 1], height[i - 1]);
        }

        r[n - 1] = 0;
        for(int i = n - 2; i >= 0; i--){
            r[i] = max(r[i + 1], height[i + 1]);
        }

        int v = 0;
        for(int i = 0; i < n; i++){
            int water = min(l[i], r[i]) - height[i];
            res[i] = water > 0? water : 0;
            v += res[i];
        }

        return v;
    }
};

滑动窗口

滑动窗口万能模板

int left = 0, right = 0;
while (right < nums.size()) {
    // 扩展右边界
    window 加入 nums[right];
    right++;

    // 当窗口不满足条件时，收缩左边界
    while (窗口不合法) {
        window 移出 nums[left];
        left++;
    }

    // 此时窗口满足条件，可以更新答案
    // res = ...
}

1.无重复字符的最长子串

Leetcode 热题 100 —— 无重复字符的最长子串

m1.c++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        // 利用set实现重复元素的判断
        unordered_set<char> st;
        int l = 0, res = 0;
        for(int r = 0; r < n; r++){
            // st = [a(l) b c] a(r), st维护的是[a, b, c], 当s[r]出现在st中，l左指针就要发挥作用了
            while(l < r && st.count(s[r]) != 0){
                st.erase(s[l++]);
            }
            st.insert(s[r]);
            res = max(res, r - l + 1);
        }

        return res;
    }
};

2.找到字符串中所有字母异位词

Leetcode 热题 100 —— 找到字符串中所有字母异位词

注

以下题目都可以利用词频的方式解决

有效的字母异位词

字符串的排列

m0.c++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int p_size = p.size(), s_size = s.size();
        vector<int> cnt_p(128, 0);
        for(int i = 0; i < p_size; i++){
            cnt_p[p[i]]++;
        }

        vector<int> cnt_s(128, 0);

        vector<int> res;
        for(int i = 0; i < s_size; i++){
            cnt_s[s[i]]++;
            if(i >= p_size) cnt_s[s[i - p_size]]--;
            if(cnt_p == cnt_s){
                res.push_back(i - p_size + 1);
            }
        }
        return res;
    }
};

m1.c++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.size(), k = p.size();
        if(k > n){
            return {};
        }
        // 利用词频的概念来实现异位词，在利用滑动窗口实现找寻符合要求的字符串的初始索引
        vector<int> cntp(26, 0), cnts(26, 0);
        vector<int> res;
        for(auto s : p){
            cntp[s - 'a']++;
        }
        for(int i = 0;i < k; i++){
            cnts[s[i] - 'a']++;
        }

        if(cntp == cnts) res.push_back(0);

        for(int i = k; i < n; i++){
            cnts[s[i] - 'a']++;
            cnts[s[i - k] - 'a']--;
            if(cntp == cnts){
                res.push_back(i - k + 1);
            }
        }
        return res;
    }
};

子串

1.和为 K 的子数组

Leetcode 热题 100 —— 和为 K 的子数组

m1.c++

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // key: 前缀和 | value: 前缀和出现的次数
        unordered_map<int, int> mp;
        mp[0] = 1;
        int sum = 0, res = 0;
        for(auto num : nums){
            sum += num;
            if(mp.count(sum - k)){
                res += mp[sum - k];
            }
            mp[sum]++;
        }
        return res;
    }
};

2.滑动窗口最大值

Leetcode 热题 100 —— 滑动窗口最大值

m1.c++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> dq;
        vector<int> res;
        for(int i = 0; i < n; i++){
            while(!dq.empty() && nums[i] >= nums[dq.back()]){
                dq.pop_back();
            }
            dq.push_back(i);

            if(dq.front() < i - k + 1){
                dq.pop_front();
            }
            if(i >= k - 1){
                res.push_back(nums[dq.front()]);
            }
        }

        return res;
    }
};

普通数组

1.最大子数组和

Leetcode 热题 100 —— 最大子数组和

m1.c++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];

        int res = nums[0];
        for(int i = 1; i < n; i++){
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            res = max(res, dp[i]);
        }

        return res;
    }
};

2.合并区间

Leetcode 热题 100 —— 合并区间

m1.c++

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> res;
        res.push_back(intervals[0]);

        for(int i = 1; i < n; i++){
            if(res.back()[1] >= intervals[i][0]){
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }else{
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

3.轮转数组

Leetcode 热题 100 —— 轮转数组

m1.c++

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res(n);
        for(int i = 0; i < n; i++){
            res[(i + k) % n] = nums[i];
        }

        for(int i = 0; i < n; i++){
            nums[i] = res[i];
        }
    }
};

4.除自身以外数组的乘积

Leetcode 热题 100 —— 除自身以外数组的乘积

m1.c++

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // l[0] = 1 | l[i] = l[i - 1] * nums[i - 1]
        int n = nums.size();
        vector<int> l(n), r(n), res(n);
        l[0] = r[n - 1] = 1;
        for(int i = 1; i < n; i++){
            l[i] = l[i - 1] * nums[i - 1];
        }

        for(int i = n - 2; i >= 0; i--){
            r[i] = r[i + 1] * nums[i + 1];
        }

        for(int i = 0; i < n; i++){
            l[i] = l[i] * r[i];
            res[i] = l[i];
        }
        return res;

    }
};

4.缺失的第一个正数

Leetcode 热题 100 —— 缺失的第一个正数

m1.c++

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //answer in [1, n + 1]
        int n = nums.size();
        for(int i = 0; i < n; i++){
            while(nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        for(int i = 0; i < n; i++){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }

        return n + 1;
    }
};

矩阵

1.矩阵置零

Leetcode 热题 100 —— 矩阵置零

m1.c++

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<bool> row(matrix.size()), col(matrix[0].size());
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(matrix[i][j] == 0){
                    row[i] = col[j] = true;
                }
            }
        }

        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(row[i] || col[j]){
                    matrix[i][j] = 0;
                }
            }
        }

    }
};

二分查找

1.搜索插入位置

Leetcode 热题 100 —— 搜索插入位置

m1.c++

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //只有找到的数一定存在，才是没有等于好的形式
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            int x = nums[mid];
            if(x == target){
                return mid;
            }else if(x < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return l;
    }
};

2.搜索二维矩阵

Leetcode 热题 100 —— 搜索二维矩阵

m1.c++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();

        int l = 0, r = row * col - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            int x = matrix[mid / col][mid % col];
            if(x == target){
                return true;
            }else if(x < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return false;
    }
};

3.在排序数组中查找元素的第一个和最后一个位置

Leetcode 热题 100 —— 在排序数组中查找元素的第一个和最后一个位置

m1.c++

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        int index_right = -1, index_left = -1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            int x = nums[mid];
            if(x <= target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
            if(x == target) index_right = mid;
        }

        l = 0, r = n - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            int x = nums[mid];
            if(x < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
            if(x == target) index_left = mid;
        }

        return {index_left, index_right};
    }
};

4.在排序数组中查找元素的第一个和最后一个位置

Leetcode 热题 100 —— 在排序数组中查找元素的第一个和最后一个位置

m1.c++

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        int index_right = -1, index_left = -1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            int x = nums[mid];
            if(x <= target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
            if(x == target) index_right = mid;
        }

        l = 0, r = n - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            int x = nums[mid];
            if(x < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
            if(x == target) index_left = mid;
        }

        return {index_left, index_right};
    }
};

5.搜索旋转排序数组

Leetcode 热题 100 —— 搜索旋转排序数组

m1.c++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            int x = nums[mid];
            if(x == target){
                return mid;
            }

            if(nums[l] <= x){
                if(nums[l] <= target && target < x){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }else{
                if(x < target && target <= nums[r]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
        }

        return -1;
    }
};

6.寻找旋转排序数组中的最小值

Leetcode 热题 100 —— 寻找旋转排序数组中的最小值

problem: m1.c++

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        /**
        怎么确定最小值点，最小值点一定在无序的部分产生；
        left < right => left <= mid < right
        选择nums[r], 因为nums[mid] != nums[right]，永远知道最小值在哪一侧
        但是 nums[mid] == nums[left]; 1 2 3 4 5 6 | 2 3 4 5 6 1, 无法判断哪一侧有序
        */
        while(l < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] < nums[r]){
                r = mid;
            }else{
                // 456 123
                l = mid + 1;
            }
        }

        return nums[l];
    }
};

problem2: m1.c++

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] < nums[r]){
                r = mid;
            }else if(nums[mid] > nums[r]){
                l = mid + 1;
            }else{
                r--;
            }
        }

        return nums[l];
    }
};

二叉树

1.二叉树的中序遍历

Leetcode 热题 100 —— 二叉树的中序遍历

m1.c++

class Solution {
public:
    void inorder(TreeNode *root, vector<int> &res){
        if(!root){
            return;
        }

        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};

m2.c++

class Solution {
public:
    void inorder(TreeNode *root, vector<int> &res){
        if(!root){
            return;
        }

        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};

m3.c++

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        /**
        颜色标记法
        白色意味着还没有访问左子树，灰色表明左子树访问完毕，可以访问自身了
        */
        const int WHITE = 0, GRAY = 1;
        stack<pair<TreeNode*, int>> st;
        st.push({root, WHITE});

        while(!st.empty()){
            auto [node, color] = st.top();
            // 因为他后面要变为灰的了，所以先把白的去掉，要不然之后又有白的、又有灰的
            st.pop();

            if(node == nullptr){
                continue;
            }

            if(color == WHITE){
                st.push({node->right, WHITE});
                st.push({node, GRAY});
                st.push({node->left, WHITE});
            }else{
                res.push_back(node->val);
            }
        }

        return res;
    }
};

[!note] > 颜色标记法，一种通用且简明的树遍历方法

因此，我在这里介绍一种 “颜色标记法” （瞎起的名字……），兼具栈迭代方法的高效，又像递归方法一样简洁易懂，更重要的是，这种方法对于前序、中序、后序遍历，能够写出完全一致的代码。 其核心思想如下：

• 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
• 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
• 如果遇到的节点为灰色，则将节点的值输出。

2.二叉树的最大深度

Leetcode 热题 100 —— 二叉树的最大深度

m1.c++

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

m2.c++

class Solution {
public:
    int maxDepth(TreeNode* root) {
        /**
        颜色标记法，通过dp的思想，实现最大深度的统计；
        这里的入栈，得先让根节点入栈，后续再让左节点和右节点入栈；
        */
        const int WHITE = 0, GRAY = 1;
        stack<pair<TreeNode*, int>> st;
        st.push({root, WHITE});
        int max_h = 0;
        unordered_map<TreeNode*, int> mp_depth;

        while(!st.empty()){
            auto [node, color] = st.top();
            st.pop();

            if(node == nullptr){
                continue;
            }

            if(color == WHITE){
                st.push({node, GRAY});
                st.push({node->right, WHITE});
                st.push({node->left, WHITE});
            }else{
                int left_h = node->left? mp_depth[node->left] : 0;
                int right_h = node->right? mp_depth[node->right] : 0;
                mp_depth[node] = max(left_h, right_h) + 1;
                max_h = max(max_h, mp_depth[node]);
            }
        }

        return max_h;
    }
};

3.翻转二叉树

Leetcode 热题 100 —— 翻转二叉树

m1.c++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<pair<TreeNode* ,bool>> st;
        st.push({root, false});

        while(!st.empty()){
            auto [node, flag] = st.top();
            st.pop();
            //结点为空，则跳过此次循环
            if(node == nullptr){
                continue;
            }

            if(!flag){
                st.push({node, true});
                st.push({node->right, false});
                st.push({node->left, false});
            }else{
                swap(node->left, node->right);
            }
        }
        return root;
    }
};

m2.c++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        stack<TreeNode*> st;
        st.push(root);

        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();

            // 交换左右子树
            swap(node->left, node->right);

            // 注意：先右再左压栈，保持顺序一致
            if (node->left) st.push(node->left);
            if (node->right) st.push(node->right);
        }

        return root;
    }
};

4.对称二叉树

Leetcode 热题 100 —— 对称二叉树

m1.c++

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        stack<pair<TreeNode*, TreeNode*>> st;
        st.push({root->left, root->right});
        while(!st.empty()){
            auto [n1, n2] = st.top();
            st.pop();
            if(!n1 && !n2){
                continue;
            }
            if(!n1 || !n2 || n1->val != n2->val){
                return false;
            }

            st.push({n1->right, n2->left});
            st.push({n1->left, n2->right});
        }
        return true;
    }
};

5.二叉树的直径

Leetcode 热题 100 —— 二叉树的直径

m1.c++

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        const int WHITE = 0, GRAY = 1;
        stack<pair<TreeNode*, int>> st;
        st.push({root, WHITE});

        unordered_map<TreeNode*, int> mp;
        int max_h = 0;
        while(!st.empty()){
            auto [node, color] = st.top();
            st.pop();

            if(node == nullptr) {
                continue;
            }

            if(color == WHITE){
                st.push({node, GRAY});
                st.push({node->right, WHITE});
                st.push({node->left, WHITE});
            }else{
                int left_h = node->left? mp[node->left] : 0;
                int right_h = node->right? mp[node->right] : 0;
                mp[node] = max(left_h, right_h) + 1;
                max_h = max(max_h, mp[node->left] + mp[node->right]);
            }
        }

        return max_h;
    }
};

6.二叉树的层序遍历

Leetcode 热题 100 —— 二叉树的层序遍历

m1.c++

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        stack<tuple<TreeNode*, bool, int>> st;
        st.push({root, false, 0});

        vector<vector<int>> res;
        while(!st.empty()){
            auto [node, flag, depth] = st.top();
            st.pop();

            if(!node){
                continue;
            }

            if(!flag){
                st.push({node, true, depth});
                st.push({node->right, false, depth + 1});
                st.push({node->left, false, depth + 1});
            }else{
                if(res.size() <= depth){
                    res.resize(depth + 1);
                }
                res[depth].push_back(node->val);
            }
        }

        return res;
    }
};

m2.c++

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        stack<tuple<TreeNode*, int>> st;
        st.push({root, 0});

        vector<vector<int>> res;
        while(!st.empty()){
            auto [node, depth] = st.top();
            st.pop();

            if(!node){
                continue;
            }

            st.push({node->right, depth + 1});
            st.push({node->left, depth + 1});

            if(res.size() <= depth){
                res.resize(depth + 1);
            }
            res[depth].push_back(node->val);
        }

        return res;
    }
};

8.验证二叉搜索树

Leetcode 热题 100 —— 验证二叉搜索树

m1.c++

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<pair<TreeNode*, int>> st;
        st.push({root, false});
        // 使用long long 防止数据溢出
        long long min_num = (long long)INT_MIN - 1;

        while(!st.empty()){
            auto [node, flag] = st.top();
            st.pop();
            if(!node) continue;

            if(!flag){
                // 中序遍历
                st.push({node->right, false});
                st.push({node, true});
                st.push({node->left, false});
            }else{
                // 判断是否是严格递增的中序遍历
                if(node->val <= min_num){
                    return false;
                }
                min_num = node->val;
            }
        }
        return true;
    }
};

9.二叉搜索树中第 K 小的元素

Leetcode 热题 100 —— 二叉搜索树中第 K 小的元素

m1.c++

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<pair<TreeNode*, int>> st;
        st.push({root, false});

        int index = 0;
        while(!st.empty()){
            auto [node, flag] = st.top();
            st.pop();

            if(!node) continue;
            if(!flag){
                st.push({node->right, false});
                st.push({node, true});
                st.push({node->left, false});
            }else{
                index++;
                if(index == k){
                    return node->val;
                }
            }
        }
        return 0;
    }
};

10.二叉树的右视图

Leetcode 热题 100 —— 二叉树的右视图

m1.c++

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        stack<pair<TreeNode*, int>> st;
        st.push({root, 0});

        vector<vector<int>> res;
        while(!st.empty()){
            auto [node, depth] = st.top();
            st.pop();

            if(!node) continue;

            st.push({node->right, depth + 1});
            st.push({node->left, depth + 1});

            if(res.size() <= depth){
                res.resize(depth + 1);
            }
            res[depth].push_back(node->val);
        }

        vector<int> vec;
        for(auto ele : res){
            vec.push_back(ele.back());
        }
        return vec;

    }
};

堆

1.数组中的第 K 个最大元素

Leetcode 热题 100 —— 数组中的第 K 个最大元素

m1.c++

链表

1.🍀 移除链表元素

代码随想录 —— 移除链表元素

m1.c++

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        auto dummy = new ListNode(-1, head);
        auto p = dummy;
        while(p->next){
            if(p->next->val == val){
                p->next = p->next->next;
            }else{
                p = p->next;
            }
        }
        return dummy->next;
    }
};

2.🍀 反转链表

代码随想录 —— 反转链表

m1.c++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        /**
        cur = head, pre = null
        ...
        cur->next = pre;
        pre = cur
        ...//cur还得往下走
        */
        ListNode *pre = nullptr;
        auto cur = head;
        while(cur){
            auto temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

m2.c++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head || head->next){
            return head;
        }
        // 找到最后一个结点，然后递归往上
        auto p = reverseList(head->next);

        head->next->next = head;
        head->next = nullptr;//废弃原来的正向指向
        return p;
    }
};

3.🍀 两两交换链表中的节点

代码随想录 —— 两两交换链表中的节点

m1.c++

/**
 * 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* swapPairs(ListNode* head) {
        // 以三个结点为基础，顺势交换顺序
        auto dummy = new ListNode(-1, head);
        auto p = dummy;
        while(p->next && p->next->next){
            auto a = p->next;
            auto b = p->next->next;

            a->next = b->next;
            b->next = a;
            p->next = b;

            p = a;
        }
        return dummy->next;
    }
};

4.🍀 删除链表的倒数第 N 个结点

代码随想录 —— 删除链表的倒数第 N 个结点

m1.c++

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto dummy = new ListNode(0, head);

        auto slow = dummy, fast = dummy;
        for(int i = 0; i <= n;i++){
            fast = fast->next;
        }

        while(fast){
            fast = fast->next;
            slow = slow->next;
        }
        auto delete_node = slow->next;
        slow->next = slow->next->next;
        delete delete_node;

        return dummy->next;
    }
};

5.🍀 链表相交

代码随想录 —— 链表相交

m1.c++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB){
            return nullptr;
        }

        auto p1 = headA, p2 = headB;
        while(p1 != p2){
            if(p1 == nullptr){
                p1 = headB;
            }else{
                p1 = p1->next;
            }

            if(p2 == nullptr){
                p2 = headA;
            }else{
                p2 = p2->next;
            }
        }
        return p1;
    }
};

6.🍀 环形链表 II

代码随想录 —— 环形链表 II

m1.c++

/**
 * 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) {
        if(head == nullptr || head->next == nullptr){
            return nullptr;
        }
        auto fast = head, slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                slow = head;
                while(slow != fast){
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

哈希表

1.🍀 有效的字母异位词

代码随想录 —— 有效的字母异位词

m1.c++

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size()){
            return false;
        }
        vector<int> count_s(26, 0), count_p(26, 0);
        for(auto i : s){
            count_s[i - 'a']++;
        }

        for(auto i : t){
            count_p[i - 'a']++;
        }

        return count_s == count_p;
    }
};

2.🍀 两个数组的交集

代码随想录 —— 两个数组的交集

m1.c++

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> st;
        for(auto i : nums1){
            st.insert(i);
        }

        vector<int> res;
        for(auto i : nums2){
            if(st.count(i)){
                st.erase(i);
                res.push_back(i);
            }
        }
        return res;
    }
};

3.🍀 快乐数

代码随想录 —— 快乐数

m1.c++

class Solution {
public:
    int bitSquareSum(int n){
        int sum = 0, mod = 0;
        while(n){
            mod =n % 10;
            sum += mod * mod;
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        unordered_set<int> st;
        while(true){
            if(n == 1) return true;
            if(st.count(n)){
                return false;
            }
            st.insert(n);
            n = bitSquareSum(n);
        }
    }
};

4.🍀 两数之和

代码随想录 —— 两数之和

m1.c++

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> mp;
        for(int i = 0; i < nums1.size(); i++){
            for(int j = 0; j < nums2.size(); j++){
                mp[nums1[i] + nums2[j]]++;// 记录数之和的频数
            }
        }

        int cnt = 0;
        for(int i = 0; i < nums3.size(); i++){
            for(int j = 0; j < nums4.size(); j++){
                int find_num = - nums3[i] - nums4[j];
                if(mp.find(find_num) != 0){
                    cnt += mp[find_num];
                }
            }
        }
        return cnt;
    }
};

5.🍀 三数之和

代码随想录 —— 三数之和

m1.c++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;

        // fix a num
        for(int i = 0; i < n - 2; i++){
            int find_num = -nums[i];
            if(i >= 1 && nums[i] == nums[i - 1]) continue;

            // two ptr
            int l = i + 1, r = n - 1;
            while(l < r){
                int sum = nums[l] + nums[r];
                if(sum == find_num){
                    res.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    while(nums[l] == nums[l - 1] && l < r){
                        l++;
                    }
                    r--;
                    while(nums[r] == nums[r + 1] && l < r){
                        r--;
                    }
                }else if(nums[l] + nums[r] < find_num){
                    l++;
                }else{
                    r--;
                }
            }
        }

        return res;
    }
};

反转字符串

1.🍀 反转字符串

代码随想录 —— 有效的字母异位词

m1.c++

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        int l = 0, r = n - 1;
        while(l < r){
            swap(s[l++], s[r--]);
        }
    }
};

m2.c++

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for(int i = 0; i < n / 2; i++){
            swap(s[i], s[n - i - 1]);
        }
    }
};

2.🍀 反转字符串 II

代码随想录 —— 反转字符串 II

m1.c++

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        int l = 0, r = n - 1;
        while(l < r){
            swap(s[l++], s[r--]);
        }
    }
};

3.🍀 反转字符串中的单词

代码随想录 —— 反转字符串中的单词

m1.c++

class Solution {
public:
    string reverseWords(string s) {
        stack<string> st;
        string word;
        s += " ";
        for(auto ss : s){
            if(ss != ' '){
                word += ss;
            }else if(!word.empty()){
                st.push(word);
                word = "";
            }
        }

        string res;
        while(!st.empty()){
            if(st.size() != 1){
                res += st.top() + " ";
            }else{
                res += st.top();
            }
            st.pop();
        }
        return res;
    }
};

4.🍀 找出字符串中第一个匹配项的下标

代码随想录 —— 找出字符串中第一个匹配项的下标

m1.c++

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size();
        int m = needle.size();
        // n - 1 - index + 1 = m; index = n - m
        for(int i = 0; i <= n - m; i++){
            int cnt = 0;
            for(int j = 0; j < m; j++){
                // haystack[i + j] == needle[j]
                if(haystack[i + j] == needle[j]){
                    cnt++;
                }
            }

            if(cnt == m){
                return i;
            }
        }
        return -1;
    }
};

双指针

1.🍀 移除元素

代码随想录 —— 移除元素

m1.c++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != val){
                swap(nums[k++], nums[i]);
            }
        }
        return k;
    }
};

2.🍀 反转字符串

代码随想录 —— 反转字符串

m1.c++

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        int l = 0, r = n - 1;
        while(l < r){
            swap(s[l++], s[r--]);
        }
    }
};

3.🍀 反转链表

代码随想录 —— 反转链表

m1.c++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr;
        ListNode *cur = head;
        while(cur){
            auto temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

栈和队列

1.🍀 用栈实现队列

代码随想录 —— 用栈实现队列

m1.c++

class MyQueue {
public:
    stack<int> stIn, stOut;
    MyQueue() {

    }

    void push(int x) {
        stIn.push(x);
    }

    int pop() {
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int res = stOut.top();
        stOut.pop();
        return res;
    }

    int peek() {
        int res = this->pop();
        stOut.push(res);
        return res;
    }

    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

2.🍀 用队列实现栈

代码随想录 —— 用栈实现队列

m1.c++

class MyStack {
public:
    queue<int> q;
    MyStack() {

    }

    void push(int x) {
        q.push(x);
    }

    int pop() {
        int n = q.size() - 1;
        while(n--){
            q.push(q.front());
            q.pop();
        }
        int ele = q.front();
        q.pop();
        return ele;
    }

    int top() {
        int ele = this->pop();
        q.push(ele);
        return ele;
    }

    bool empty() {
        return q.empty();
    }
};

3.🍀 有效的括号

代码随想录 —— 用栈实现队列

m1.c++

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(auto ss : s){
            if(ss == '[' || ss == '(' || ss == '{'){
                st.push(ss);
            }else{
                // prevent nullptr: probably right ptr -> st
                if(st.empty()) return false;
                auto t = st.top();
                if(ss == ']' && t == '[' || ss == '}' && t == '{' || ss == ')' && t == '('){
                    st.pop();
                }else{
                    return false;
                }
            }
        }

        return st.empty();
    }
};

4.🍀 删除字符串中的所有相邻重复项

代码随想录 —— 用栈实现队列

m1.c++

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(auto ss : s){
            if(ss == '[' || ss == '(' || ss == '{'){
                st.push(ss);
            }else{
                // prevent nullptr: probably right ptr -> st
                if(st.empty()) return false;
                auto t = st.top();
                if(ss == ']' && t == '[' || ss == '}' && t == '{' || ss == ')' && t == '('){
                    st.pop();
                }else{
                    return false;
                }
            }
        }

        return st.empty();
    }
};

5.🍀 滑动窗口最大值

代码随想录 —— 滑动窗口最大值

m1.c++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;// store index
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
            while(!q.empty() && nums[i] >= nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);

            // q.front() store the max val
            if(q.front() < i - k + 1){
                q.pop_front();
            }
            // i -> [i - k + 1, i], start record val
            if(i - k + 1 >= 0){
                res.push_back(nums[q.front()]);
            }

        }
        return res;
    }
};

6.🍀 滑动窗口最大值

代码随想录 —— 滑动窗口最大值

m1.c++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;// store index
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
            while(!q.empty() && nums[i] >= nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);

            // q.front() store the max val
            if(q.front() < i - k + 1){
                q.pop_front();
            }
            // i -> [i - k + 1, i], start record val
            if(i - k + 1 >= 0){
                res.push_back(nums[q.front()]);
            }

        }
        return res;
    }
};

7.🍀 前 K 个高频元素

代码随想录 —— 前 K 个高频元素

m1.c++

class Solution {
public:
    static bool cmp(pair<int,int>& a, pair<int,int>& b) {
        return a.first > b.first;   // 按频率从大到小
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++){
            mp[nums[i]]++;
        }

        vector<pair<int, int>> v;
        for(auto ele : mp){
            v.push_back({ele.second, ele.first});
        }

        sort(v.begin(), v.end(), cmp);
        vector<int> res;
        for(int i = 0; i < k; i++){
            res.push_back(v[i].second);
        }
        return res;
    }
};

数组

1.🍀 二分查找

代码随想录 —— 二分查找

m1.c++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            int x = nums[mid];
            if(x == target){
                return mid;
            }else if(x < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return -1;
    }
};

2.🍀 移除元素

代码随想录 —— 移除元素

m1.c++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != val){
                swap(nums[k++], nums[i]);
            }
        }
        return k;
    }
};

3.🍀 有序数组的平方

代码随想录 —— 有序数组的平方

m1.c++

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        int pos = n - 1;
        vector<int> res(n);
        while(pos >= 0){
            int left = nums[l] * nums[l];
            int right = nums[r] * nums[r];
            if(left < right){
                res[pos--] = right;
                r--;
            }else{
                res[pos--] = left;
                l++;
            }
        }
        return res;
    }
};

4.🍀 有序数组的平方

代码随想录 —— 长度最小的子数组

m1.c++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int left = 0;
        int min_len = INT_MAX;
        for(int i = 0; i < n; i++){
            sum += nums[i];
            while(sum >= target){
                min_len = min(min_len, i - left + 1);
                sum = sum - nums[left];
                left++;
            }
        }
        return min_len == INT_MAX? 0 : min_len;
    }
};

二叉树

1.🍀 二叉树的前序遍历

代码随想录 —— 二叉树的前序遍历

m1.c++

class Solution {
public:
    void preOrder(TreeNode *root, vector<int> &res){
        if(!root){
            return;
        }
        res.push_back(root->val);
        preOrder(root->left, res);
        preOrder(root->right, res);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preOrder(root, res);
        return res;
    }
};

m2.c++

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        st.push(root);
        vector<int> res;
        while(!st.empty()){
            auto node = st.top();
            st.pop();
            if(!node) continue;

            res.push_back(node->val);
            st.push(node->right);
            st.push(node->left);
        }
        return res;
    }
};

m3.c++

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        const int WHITE = 0, GRAY = 1;
        stack<pair<TreeNode*, int>> st;
        st.push({root, WHITE});
        vector<int> res;
        while(!st.empty()){
            auto [node, color] = st.top();
            st.pop();
            if(!node) continue;

            if(color == WHITE){
                st.push({node->right, WHITE});
                st.push({node->left, WHITE});
                st.push({node, GRAY});
            }else{
                res.push_back(node->val);
            }
        }
        return res;
    }
};

2.🍀 二叉树的中序遍历

代码随想录 —— 二叉树的中序遍历

m1.c++

class Solution {
public:
    void inOrder(TreeNode *node, vector<int> &res){
        if(!node) return;
        inOrder(node->left, res);
        res.push_back(node->val);
        inOrder(node->right, res);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inOrder(root, res);
        return res;
    }
};

m2.c++

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        const int WHITE = 0, GRAY = 1;
        stack<pair<TreeNode*, int>> st;
        st.push({root, WHITE});
        vector<int> res;
        while(!st.empty()){
            auto [node, color] = st.top();
            st.pop();
            if(!node) continue;

            if(color == WHITE){
                st.push({node->right, WHITE});
                st.push({node, GRAY});
                st.push({node->left, WHITE});
            }else{
                res.push_back(node->val);
            }
        }
        return res;
    }
};

3.🍀 二叉树的后序遍历

代码随想录 —— 二叉树的后序遍历

m1.c++

class Solution {
public:
    void postOrder(TreeNode *node, vector<int> &res){
        if(!node) return;
        postOrder(node->left, res);
        postOrder(node->right, res);
        res.push_back(node->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postOrder(root, res);
        return res;
    }
};

m2.c++

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        const int WHITE = 0, GRAY = 1;
        stack<pair<TreeNode*, int>> st;
        st.push({root, WHITE});
        vector<int> res;
        while(!st.empty()){
            auto [node, color] = st.top();
            st.pop();
            if(!node) continue;

            if(color == WHITE){
                st.push({node, GRAY});
                st.push({node->right, WHITE});
                st.push({node->left, WHITE});
            }else{
                res.push_back(node->val);
            }
        }
        return res;
    }
};

4.🍀 二叉树的层序遍历

代码随想录 —— 二叉树的层序遍历

m1.c++

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root){
            return res;
        }

        queue<TreeNode*> q;
        q.push(root);
        // bfs
        while(!q.empty()){
            int size = q.size();
            vector<int> level_vals;
            for(int i = 0; i < size; i++){
                auto node = q.front();
                q.pop();

                level_vals.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(level_vals);
        }
        return res;
    }
};

m2.c++

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        const int WHITE = 0, GRAY = 1;
        stack<tuple<TreeNode*, int, int>> st;
        st.push({root, WHITE, 0});

        vector<vector<int>> res;
        while(!st.empty()){
            auto [node, color, depth] = st.top();
            st.pop();
            if(!node) continue;

            if(color == WHITE){
                st.push({node, GRAY, depth});
                st.push({node->right, WHITE, depth + 1});
                st.push({node->left, WHITE, depth + 1});
            }else{
                if(res.size() <= depth){
                    res.resize(depth + 1);
                }
                res[depth].push_back(node->val);
            }
        }
        return res;
    }
};

m3.c++

class Solution {
public:
    int getHeight(TreeNode* root){
        if(!root){
            return 0;
        }
        int l = getHeight(root->left);
        int r = getHeight(root->right);
        return 1 + max(l ,r);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        const int WHITE = 0, GRAY = 1;
        stack<tuple<TreeNode*, int, int>> st;
        st.push({root, WHITE, 0});

        int h = getHeight(root);
        vector<vector<int>> res(h);
        while(!st.empty()){
            auto [node, color, depth] = st.top();
            st.pop();
            if(!node) continue;

            if(color == WHITE){
                st.push({node, GRAY, depth});
                st.push({node->right, WHITE, depth + 1});
                st.push({node->left, WHITE, depth + 1});
            }else{
                res[depth].push_back(node->val);
            }
        }
        return res;
    }
};

5.🍀 二叉树的层序遍历 II

代码随想录 —— 二叉树的层序遍历 II

m1.c++

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        vector<vector<int>> res;
        if(!root){
            return res;
        }
        while(!q.empty()){
            int size = q.size();
            vector<int> level_vals;
            for(int i = 0; i < size; i++){
                auto node = q.front();
                q.pop();
                level_vals.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.insert(res.begin(), level_vals);
        }
        return res;

    }
};

m2.c++

class Solution {
public:
    int getHeight(TreeNode *root){
        if(!root){
            return 0;
        }
        int l = getHeight(root->left);
        int r = getHeight(root->right);
        return 1 + max(l, r);
    }

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        int h = getHeight(root);
        vector<vector<int>> res(h);
        const int WHITE = 0, GRAY = 1;
        stack<tuple<TreeNode*, int, int>> st;
        st.push({root, WHITE, 0});
        while(!st.empty()){
            auto [node, color, depth] = st.top();
            st.pop();
            if(!node) continue;

            if(color == WHITE){
                st.push({node, GRAY, depth});
                st.push({node->right, WHITE, depth + 1});
                st.push({node->left, WHITE, depth + 1});
            }else{
                int index = h - depth - 1;
                res[index].push_back(node->val);
            }
        }
        return res;

    }
};

6.🍀 二叉树的右视图

代码随想录 —— 二叉树的右视图

m1_queue.c++

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        vector<int> res;
        if(!root){
            return res;
        }
        while(!q.empty()){
            int size = q.size();
            int level_r_val;
            for(int i = 0; i < size; i++){
                auto node = q.front();
                q.pop();
                level_r_val = node->val;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(level_r_val);
        }
        return res;
    }

};

m2_stack.c++

class Solution {
public:
    int getHeight(TreeNode *node){
        if(!node) return 0;
        int l = getHeight(node->left);
        int r = getHeight(node->right);
        return 1 + max(l, r);
    }
    vector<int> rightSideView(TreeNode* root) {
        stack<pair<TreeNode*, int>> st;
        st.push({root, 0});

        vector<int> res(getHeight(root));
        while(!st.empty()){
            auto [node ,depth] = st.top();
            st.pop();
            if(!node) continue;

            st.push({node->right, depth + 1});
            st.push({node->left, depth + 1});

            res[depth] = node->val;
        }
        return res;
    }

};

7.🍀 翻转二叉树

代码随想录 —— 二叉树的层平均值

m1.c++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        st.push(root);

        while(!st.empty()){
            auto node = st.top();
            st.pop();

            if(!node) continue;

            st.push(node->right);
            st.push(node->left);

            swap(node->left, node->right);
        }
        return root;
    }
};

m1.c++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root){
            return nullptr;
        }
        auto l = invertTree(root->left);
        auto r = invertTree(root->right);
        root->left = r;
        root->right = l;
        return root;
    }
};

8.🍀 对称二叉树

代码随想录 —— 对称二叉树

m1.c++

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        stack<pair<TreeNode*, TreeNode*>> st;
        st.push({root->left, root->right});
        while(!st.empty()){
            auto [a, b] = st.top();
            st.pop();

            if(!a && !b){
                continue;
            }

            if(!a || !b || a->val != b->val){
                return false;
            }
            st.push({a->left, b->right});
            st.push({a->right, b->left});
        }
        return true;
    }
};

9.🍀 二叉树的最大深度

代码随想录 —— 二叉树的最大深度

m1.c++

class Solution {
public:
    int maxDepth(TreeNode* root) {
       if(!root){
        return 0;
       }
       int l = maxDepth(root->left);
       int r = maxDepth(root->right);
       return 1 + max(l, r);
    }
};

m2.c++

class Solution {
public:
    int maxDepth(TreeNode* root) {
       stack<pair<TreeNode*, int>> st;
       st.push({root, 1});

       int max_depth = 0;
       while(!st.empty()){
            auto [node, depth] = st.top();
            st.pop();

            if(!node) continue;
            // node == nullptr, not count depth
            max_depth = max(max_depth, depth);

            st.push({node->right, depth + 1});
            st.push({node->left, depth + 1});
       }

       return max_depth;
    }
};

10.🍀 二叉树的最小深度

代码随想录 —— 二叉树的最小深度

m1.c++

class Solution {
public:
    int minDepth(TreeNode* root) {
        stack<pair<TreeNode*, int>> st;
        st.push({root, 1});
        int min_depth = INT_MAX;
        while(!st.empty()){
            auto [node, depth] = st.top();
            st.pop();
            if(!node) continue;

            if(!node->left && !node->right){
                min_depth = min(min_depth, depth);
            }
            st.push({node->right, depth + 1});
            st.push({node->left, depth + 1});
        }
        return min_depth;
    }
};

m2.c++

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root){
            return 0;
        }
        int l = minDepth(root->left);
        int r = minDepth(root->right);

        if(l == 0) return r + 1;
        if(r == 0) return l + 1;

        return 1 + min(l , r);
    }
};

贡献者: paiad