标签：return 入门 val int nullptr 节点 数据结构 root LeetCode

数据结构入门

217 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

解法 1：两层循环

第一层循环遍历数组元素，第二层循环同样遍历数组元素，当两者相同时返回 true。超时。

解法 2：带存储的循环

创建临时数组。循环遍历数组元素，再遍历临时数组，如果临时数组中没有该元素，则加入数组中。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        vector<int> bases{nums[0]};
        for (int i = 1; i < nums.size(); ++i) {
            for (int base : bases) {
                if (nums[i] == base) {
                    return true;
                } else {
                    bases.push_back(nums[i]);
                }
            }
        }
        return false;
    }
};

执行出错信息 ERROR: AddressSanitizer: heap-use-after-free。错误在于当使用了 push_back() 函数后，vector 可能因为容量不足而创建新的向量对象，这时之前的对象已经被销毁，引用自然也失效了。但该问题仅出现在 LeetCode 网站编译器上，本地 MSVC 编译成功且可以运行。即使成功应该也会导致超时。

解法 3：排序后查找

将数组排序，再依次比较判断是否有重复元素。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
};

解法 4：哈希表

将每个元素依次在哈希表中查找，如果没有则加入哈希表中。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for (int x: nums) {
            if (s.find(x) != s.end()) {
                return true;
            }
            s.insert(x);
        }
        return false;
    }
};

53 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

解法 1：动态规划

动态规划的关键在于递归地求定义最优解的值，然后采用自底向上的方法求解。

用 \(f(i)\) 表示以第 \(i\) 个数结尾的连续子数组的最大和，那么 \(f(i)=\max(f(i-1)+nums[i],nums[i])\)。

最大值要么为前一个数组的最大值加上后一个元素，要么只是后一个元素。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int *arr = new int[nums.size()]{0};
        int value = nums[0];
        arr[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            arr[i] = max(arr[i - 1] + nums[i], nums[i]);
            value = max(arr[i], value);
        }
        return value;
    }
};

需要注意的是最后求的是最大值，需要准备元素判断并保存最大值。

1 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

解法 1：哈希表

创建一个哈希表保存所有数据，再遍历哈希表找是否有元素与当前遍历值和为 target 的元素。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans{};
        unordered_map<int, int> map{};
        for (int i = 0; i < nums.size(); ++i) {
            map.insert({nums[i], i});
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (map.find(target - nums[i]) != map.end()) {
                int second = map.find(target - nums[i])->second;
                if (i != second) {
                    ans.push_back(i);
                    ans.push_back(second);
                    return ans;
                }
            }
        }
        return ans;
    }
};

注意在 unordered_map 中，pair 的前一个值为 find() 函数的目标，后一个值为附带的信息。还需要注意防止 [3, 2, 4] 导致的重复数据。

88 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解法 1：复制数组再合并

在直接将两数组合并时发现难以控制中途的各种问题，于是构造一个新的 nums1 再进行合并。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> temp_nums1(m);
        copy(nums1.begin(), nums1.begin() + m, temp_nums1.begin());

        int nums1_index = 0;
        int nums2_index = 0;
        int i = 0;
        while (nums1_index != m && nums2_index != n) {
            if (temp_nums1[nums1_index] >= nums2[nums2_index]) {
                nums1[i] = nums2[nums2_index];
                nums2_index++;
            } else {
                nums1[i] = temp_nums1[nums1_index];
                nums1_index++;
            }
            i++;
        }

        int final_index = nums1_index + nums2_index;
        if (nums1_index == m) {
            copy(nums2.begin() + nums2_index, nums2.end(), nums1.begin() + final_index);
        }
        if (nums2_index == n) {
            copy(temp_nums1.begin() + nums1_index, temp_nums1.end(), nums1.begin() + final_index);
        }
    }
};

解法 2：合并后排序

直接复制合并后使用内置 sort() 方法排序。

350 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

解法 1：哈希表

将第一个数组中每个出现的数存入哈希表并记录出现的次数，再遍历第二个数组，如果表中存在当前遍历的元素，则将该数加入结果中并将哈希表中的记录次数减一。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.empty() || nums2.empty()) {
            return vector<int>{};
        }

        unordered_map<int, int> map;
        for (int x : nums1) {
            auto iter = map.find(x);
            if (iter == map.end()) {
                map.insert({x, 1});
            } else {
                iter->second++;
            }
        }

        vector<int> ans{};
        for (int x : nums2) {
            auto iter = map.find(x);
            if (iter != map.end()) {
                ans.emplace_back(x);
                iter->second--;
                if (iter->second == 0) {
                    map.erase(x);
                }
            }
        }

        return ans;
    }
};

注意观察题目是否要求连续，map 中元素的 second 可以用来记录额外的值，这道题记录了次数。

121 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解法 1：暴力破解

对于第 i 天卖出的股票来说，可以获得的最大利润为第 i 天价格减掉前 i-1 天中最低价格的差。计算出每个第 i 天卖出时的最高利润比较即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int *arr = new int[prices.size()]{0};
        arr[0] = 0;
        set<int> min_set;
        min_set.insert(prices[0]);

        for (int i = 1; i < prices.size(); ++i) {
            min_set.insert(prices[i]);
            arr[i] = prices[i] - *min_set.begin();
        }

        int ans = 0;
        for (int i = 0; i < prices.size(); ++i) {
            ans = ans > arr[i] ? ans : arr[i];
        }
        return ans;
    }
};

可以优化的地方在于程序只需要前 i-1 个数中最小的值，因此记录一个 minimum 即可，有点类似动态规划，将上一步计算的值保留到下一步，而不需要一整个完成的 set。

解法 2：一次遍历

主要思想同上，但如果当前值为前 i-1 天中的最小值则，否则直接计算当天卖出可以获得的利润，保存到最大值中。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;
        int minimum = prices[0];

        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] < minimum) {
                minimum = prices[i];
            } else {
                max_profit = max(prices[i] - minimum, max_profit);
            }
        }
        return max_profit;
    }
};

566 重塑矩阵

在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。

给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。

如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

解法 1：复制

将原矩阵复制到一个新向量中，再从向量复制到要求的矩阵中。

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        vector<int> arr{};
        for (vector<int> outer : mat) {
            for (int x : outer) {
                arr.emplace_back(x);
            }
        }

        if (arr.size() != r * c) {
            return mat;
        }

        vector<vector<int>> ans{};
        auto iter = arr.begin();
        for (int i = 0; i < r; ++i) {
            vector<int> temp(c);
            copy(iter, iter + c, temp.begin());
            ans.emplace_back(temp);
            iter = iter + c;
        }
        return ans;
    }
};

解法 2：映射

将原数组元素按照下标映射到新的数组中。

118 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

解法 1：根据题意写

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans{};

        ans.emplace_back(vector<int>{1});
        if (numRows == 1) {
            return ans;
        }

        ans.emplace_back(vector<int>{1,1});
        if (numRows == 2) {
            return ans;
        }

        for (int i = 3; i <= numRows; ++i) {
            vector<int> temp(i);
            temp[0] = 1;
            for (int j = 1; j < i - 1; ++j) {
                temp[j] = ans[i - 2][j - 1] + ans[i - 2][j];
            }
            temp[i - 1] = 1;
            ans.emplace_back(temp);
        }

        return ans;
    }
};

解法 2：数学

根据杨辉三角的用途利用二项式定理计算每个元素数据。

36 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

解法 1：三次遍历

将提供的元素遍历三遍，依次检查行、列和小格子。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i) {
            set<char> column_set{};
            for (int j = 0; j < 9; ++j) {
                char c = board[i][j];
                if (c == '.') {
                    continue;
                }
                if (!column_set.insert(c).second) {
                    return false;
                }
            }
        }

        for (int i = 0; i < 9; ++i) {
            set<char> line_set{};
            for (int j = 0; j < 9; ++j) {
                char c = board[j][i];
                if (c == '.') {
                    continue;
                }
                if (!line_set.insert(c).second) {
                    return false;
                }
            }
        }

        for (int i = 0; i < 9; i = i + 3) {
            for (int j = 0; j < 9; j = j + 3) {
                set<char> block_set{};
                for (int m = i; m < i + 3; ++m) {
                    for (int n = j; n < j + 3; ++n) {
                        char c = board[m][n];
                        if (c == '.') {
                            continue;
                        }
                        if (!block_set.insert(c).second) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }
};

解法 2：一次遍历

一次遍历转换下标依次存到不同的哈希表中。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<set<int>> line_sets(9);
        vector<set<int>> column_sets(9);
        vector<set<int>> block_sets(9);

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                char c = board[i][j];
                if (c == '.') {
                    continue;
                }
                if (!line_sets[i].insert(c).second) {
                    return false;
                }
                if (!column_sets[j].insert(c).second) {
                    return false;
                }
                if (!block_sets[(i / 3) * 3 + j / 3].insert(c).second) {
                    return false;
                }
            }
        }
        return true;
    }
};

73 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

解法 1：遍历并存储 0 元素

使用两个哈希表保存 0 所在的行和列，再将遍历它们并将表中对应行列元素设置为 0。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> line_set{};
        unordered_set<int> column_set{};

        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                if (matrix[i][j] == 0) {
                    line_set.insert(i);
                    column_set.insert(j);
                }
            }
        }

        for (int x : line_set) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                matrix[x][j] = 0;
            }
        }
        for (int x : column_set) {
            for (int i = 0; i < matrix.size(); ++i) {
                matrix[i][x] = 0;
            }
        }
    }
};

解法 2：两个标记变量

将第一列和第一行是否有 0 存入两个变量中，再第一行和第一列当作前面的 set 使用，最后根据两个变量决定第一行和第一列是否设置为 0。

387 字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

解法 1：哈希表

将每个字符依次加入到哈希表中，如果字符已经存在则记录值加一，最后遍历哈希表找到记录次数为 1 的不重复字符串，再查找该字符在字符串中的位置找到第一个。

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> count_map{};
        unordered_map<char, int> index_map{};
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (count_map.find(c) == count_map.end()) {
                count_map.insert({c, 1});
                index_map.insert({c, i});
            } else {
                count_map.find(c)->second++;
            }
        }

        int min_index = s.size();
        unordered_map<char, int>::iterator iter;
        for (iter = count_map.begin(); iter != count_map.end(); ++iter) {
            if (iter->second == 1) {
                int current_index = index_map.find(iter->first)->second;
                min_index = min(current_index, min_index);
            }
        }
        return (min_index == s.size() ? -1 : min_index);
    }
};

解法 2：优化的哈希表

只使用一个哈希表记录元素和它的位置。遍历字符串时，如果不存在该字符，则保存字符和它的位置；如果存在则将字符的位置设置为 -1。最后遍历哈希表找到位置不是 -1 的第一个字符位置。

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> map{};
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (map.find(c) == map.end()) {
                map.insert({c, i});
            } else {
                map.find(c)->second = -1;
            }
        }

        int min_index = s.size();
        unordered_map<char, int>::iterator iter;
        for (iter = map.begin(); iter != map.end(); ++iter) {
            if (iter->second != -1) {
                int current_index = iter->second;
                min_index = min(current_index, min_index);
            }
        }
        return (min_index == s.size() ? -1 : min_index);
    }
};

383 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

解法 1：哈希表

将 magazine 的字母存入哈希表中并记录出现的次数。再遍历 ransomNote，如果哈希表无当前字符，返回 false；如果有，记录次数减一，如果记录次数小于 0，返回 false。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> map{};
        for (char c : magazine) {
            if (map.find(c) == map.end()) {
                map.insert({c, 1});
            } else {
                map.find(c)->second++;
            }
        }
        for (char c : ransomNote) {
            if (map.find(c) == map.end()) {
                return false;
            } else {
                map.find(c)->second--;
                if (map.find(c)->second < 0) {
                    return false;
                }
            }
        }
        return true;
    }
};

242 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

解法 1：哈希表

将两个字符串中的字符存入两个哈希表中，再比较两个哈希表即可。

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> map_s;
        unordered_map<char, int> map_t;
        for (char c : s) {
            if (map_s.find(c) == map_s.end()) {
                map_s.insert({c, 1});
            } else {
                map_s.find(c)->second++;
            }
        }
        for (char c : t) {
            if (map_t.find(c) == map_t.end()) {
                map_t.insert({c, 1});
            } else {
                map_t.find(c)->second++;
            }
        }

        for (pair<char, int> p : map_s) {
            if (map_t.find(p.first) != map_t.end() && map_t.find(p.first)->second == p.second) {
                map_t.erase(p.first);
            } else {
                return false;
            }
        }
        return map_t.empty();
    }
};

141 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

解法 1：哈希表

遍历链表，将读过的节点存入哈希表中，如果表中已存在该节点，返回 true，否则加入节点。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode *> set{};
        while (head != nullptr) {
            if (set.insert(head).second) {
                head = head->next;
            } else {
                return true;
            }
        }
        return false;
    }
};

解法 2：Floyd 判圈算法

设置快慢两个指针，慢指针每次前进一步，快指针每次前进两步，如果链表中有环，快指针将优先进入环，并在某个时刻与慢指针重合。当快指针为空指针时链表不是环形链表。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        if (slow == nullptr) {
            return false;
        }
        ListNode* quick = head->next;
        while (slow != quick) {
            if (slow == nullptr || quick == nullptr || quick->next == nullptr) {
                return false;
            }
            slow = slow->next;
            quick = quick->next->next;
        }
        return true;
    }
};

注意需要判断多个指针是否为空，否则将无法访问指向的下一个指针。

21 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解法 1：改变指针合并

首先判断两个链表的第一个节点选做新链表的链表头，保留两个链表变量记录当前两链表访问的位置，再进行修改指针的合并。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* index1 = list1;
        ListNode* index2 = list2;
        auto *ans = new ListNode(0);
        auto *root = ans;
        while (index1 != nullptr && index2 != nullptr) {
            if (index1->val >= index2->val) {
                ans->next = index2;
                index2 = index2->next;
            } else {
                ans->next = index1;
                index1 = index1->next;
            }
            ans = ans->next;
        }
        if (index1 == nullptr) {
            ans->next = index2;
        }
        if (index2 == nullptr) {
            ans->next = index1;
        }
        return root->next;
    }
};

解法 2：递归

函数返回的是合并链表后最小的节点，可以利用这一点进行递归，得到当前最小的节点后连接到剩余两个链表的最小节点，直到两链表遍历到结尾。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) {
            return list2;
        } else if (list2 == nullptr) {
            return list1;
        } else if (list1->val >= list2->val) {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        } else if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
    }
};

很难自己想出来。

203 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

解法 1：常规方法

判断三种情况，删除头部节点，中部节点，尾部节点。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) {
            return nullptr;
        }
        while (head->val == val) {
            head = head->next;
            if (head == nullptr) {
                return nullptr;
            }
        }
        ListNode* root = head;

        while (head != nullptr) {
            if (head->next == nullptr) {
                return root;
            }
            if (head->next->val == val) {
                head->next = head->next->next;
            } else {
                head = head->next;
            }
        }
        return root;
    }
};

注意每个使用 node->next->val 的地方前检查 node->next 是否为空指针。小技巧：添加一个头部节点即可将原头部节点处理为中部节点。

206 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解法 1：存储数据新建链表

将链表读取一遍并保存在数组中，再倒序遍历数组创建链表。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        vector<int> arr{};
        while (head != nullptr) {
            arr.emplace_back(head->val);
            head = head->next;
        }
        auto root = new ListNode{0};
        ListNode* origin = root;
        for (int i = 0; i < arr.size(); ++i) {
            auto node = new ListNode(arr[arr.size() - i - 1]);
            root->next = node;
            root = root->next;
        }
        return origin->next;
    }
};

解法 2：迭代

按照题意存储当前节点和后一个节点，使后一个节点的 next 指向前一个节点即可。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr;
        if (head == nullptr) {
            return nullptr;
        }
        ListNode *now = head;
        if (head->next == nullptr) {
            return now;
        }
        ListNode *next = head->next;
        while (now->next != nullptr) {
            now->next = pre;
            pre = now;
            now = next;
            next = next->next;
        }
        now->next = pre;
        return now;
    }
};

83 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

解法 1：删除重复节点

设置比较指针和遍历指针，将遍历指针与比较指针对比判断是否为重复数组。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *pre = head;
        if(pre == nullptr) {
            return nullptr;
        }
        ListNode *now = head->next;
        while(now != nullptr) {
            while (pre->val == now->val) {
                pre->next = now->next;
                now = now->next;
                if (now == nullptr) {
                    return head;
                }
            }
            pre = pre->next;
            now = now->next;
        }
        return head;
    }
};

解法 2：对比删除不保留数据

取消保存 now 变量，直接将 pre->val 和 pre->next->val 对比。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *pre = head;
        if(pre == nullptr) {
            return nullptr;
        }
        while (pre->next != nullptr) {
            while (pre->val == pre->next->val) {
                pre->next = pre->next->next;
                if (pre->next == nullptr) {
                    return head;
                }
            }
            pre = pre->next;
        }
        return head;
    }
};

20 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

解法 1：栈

将左括号进栈，右括号出栈，如果最后栈为空则有效。

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 == 1) {
            return false;
        }
        stack<char> stack{};
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (stack.empty()) {
                return false;
            }

            if (c == ')') {
                if (stack.top() != '(') {
                    return false;
                } else {
                    stack.pop();
                }
            } else if (c == ']') {
                if (stack.top() != '[') {
                    return false;
                } else {
                    stack.pop();
                }
            } else if (c == '}') {
                if (stack.top() != '{') {
                    return false;
                } else {
                    stack.pop();
                }
            }
        }
        return stack.empty();
    }
};

注意需要判断第一个符号即为反括号的情况，这时 stack.pop() 会报错。

232 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

解法 1：两个栈互相导

将第一个栈中的数据导入到第二个栈，这时最下方的数据就被移动到了最上方，执行操作后再将数据导回原栈即可。

class MyQueue {
public:
    stack<int> real_stack;
    stack<int> ref_stack;

    MyQueue() {
        real_stack = stack<int>{};
        ref_stack = stack<int>{};
    }

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

    int pop() {
        if (empty()) {
            return -1;
        }
        while (!real_stack.empty()) {
            int x = real_stack.top();
            ref_stack.push(x);
            real_stack.pop();
        }
        int ans = ref_stack.top();
        ref_stack.pop();
        while (!ref_stack.empty()) {
            int x = ref_stack.top();
            real_stack.push(x);
            ref_stack.pop();
        }
        return ans;
    }

    int peek() {
        while (!real_stack.empty()) {
            int x = real_stack.top();
            ref_stack.push(x);
            real_stack.pop();
        }
        int ans = ref_stack.top();
        while (!ref_stack.empty()) {
            int x = ref_stack.top();
            real_stack.push(x);
            ref_stack.pop();
        }
        return ans;
    }

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

144 二叉树的前序遍历

解法 1：递归

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans{};
        traverse(root, ans);
        return ans;
    }

    void traverse(TreeNode* node, vector<int> &v) {
        if (node == nullptr) {
            return;
        } else {
            v.emplace_back(node->val);
            traverse(node->left, v);
            traverse(node->right, v);
        }
    }
};

解法 2：迭代

利用一个栈维护当前访问的根节点。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans{};
        if (root == nullptr) {
            return ans;
        }

        stack<TreeNode*> stack{};
        stack.emplace(root);

        while (!stack.empty()) {
            while (root != nullptr) {
                ans.emplace_back(root->val);
                stack.emplace(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            root = root->right;
        }

        return ans;
    }
};

94 二叉树的中序遍历

解法 1：递归

同上，调整三条语句。

解法 2：迭代

同上。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans{};
        if (root == nullptr) {
            return ans;
        }

        stack<TreeNode*> stack{};

        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.emplace(root);
                root = root->left;
            }
            root = stack.top();
            ans.emplace_back(root->val);
            stack.pop();
            root = root->right;
        }
        return ans;
    }
};

145 二叉树的后序遍历

解法 1：递归

同上，调整三条语句。

解法 2：迭代

同上。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans{};
        if (root == nullptr) {
            return ans;
        }

        stack<TreeNode*> stack{};
        TreeNode* prev = nullptr;
        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.emplace(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            if (root->right == nullptr || root->right == prev) {
                ans.emplace_back(root->val);
                prev = root;
                root = nullptr;
            } else {
                stack.emplace(root);
                root = root->right;
            }
        }
        return ans;
    }
};

102 二叉树的层序遍历

解法 1：广度优先搜索

建立一个队列，将当前的节点放入队列中，将当前左右子节点依次加入队列中，然后移除原始节点，依次执行直到队列为空。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans{};
        if (root == nullptr) {
            return ans;
        }

        queue<TreeNode*> queue{};
        queue.push(root);
        while (!queue.empty()) {
            int count = queue.size();
            vector<int> v{};
            for (int i = 0; i < count; ++i) {
                TreeNode* node = queue.front();
                v.emplace_back(node->val);
                if (node->left != nullptr) {
                    queue.push(node->left);
                }
                if (node->right != nullptr) {
                    queue.push(node->right);
                }
                queue.pop();
            }
            ans.emplace_back(v);
        }
        return ans;
    }
};

广度优先搜索的核心即在于构建一个队列，利用先进先出的原理存储节点数据。

104 二叉树的最大深度

解法 1：递归

节点的最大深度必然为左叶子节点和有叶子节点的最大值加一。

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

注意，不需要判断左右指针是否为空，因为第一个条件已经判断了。这也是深度优先的思想。

解法 2：广度优先搜索

方法与层序遍历一致，记录并保留最大值。

101 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

解法 1：递归

如果一个根节点发展出的树轴对称，则它的左右节点都相等且对称。对称指左叶子节点的左叶子节点要和右叶子节点的右叶子节点相等，且左叶子节点的右叶子节点和右叶子节点的左叶子节点相等。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }

    bool check(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right != nullptr) {
            return false;
        } else if (left != nullptr && right == nullptr) {
            return false;
        } else if (left == nullptr && right == nullptr) {
            return true;
        } else {
            return left->val == right->val && check(left->left, right->right) && check(left->right, right->left);
        }
    }
};

226 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

解法 1：递归

翻转二叉树也就是把树的左右叶子节点交换，并交换它们的左右叶子节点。

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

112 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

解法 1：递归

深度遍历树，如果遍历到结尾且路径和为要求值则返回 true。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        return traverse(root, 0, targetSum);
    }

    bool traverse(TreeNode* node, int sum, int targetSum) {
        if (node == nullptr) {
            return false;
        }
        sum = sum + node->val;
        if (sum == targetSum) {
            if (node->left == nullptr && node->right == nullptr) {
                return true;
            }
        }
        return traverse(node->left, sum, targetSum) || traverse(node->right, sum, targetSum);
    }
};

注意，可以简化为一个函数，每次更新时将 targetSum 改为 targetSum - root->val 即可。

700 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

解法 1：定义

二叉搜索树左节点小于父节点，右节点大于父节点。

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != nullptr) {
            if (val == root->val) {
                return root;
            } else if (val < root->val) {
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return nullptr;
    }
};

701 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

解法 1：定义

根据定义插入值。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        auto new_node = new TreeNode(val);
        if (root == nullptr) {
            return new_node;
        }

        TreeNode* ans = root;
        TreeNode* pre = nullptr;
        while (root != nullptr) {
            pre = root;
            if (val > root->val) {
                root = root->right;
            } else {
                root = root->left;
            }
        }
        if (val > pre->val) {
            pre->right = new_node;
        } else {
            pre->left = new_node;
        }
        return ans;
    }
};

98 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

解法 1：错误递归

如果二叉树某节点为有效的，那么它的左右子树都应该是有效的。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        bool left = true;
        if (root->left != nullptr) {
            left = root->val > root->left->val && isValidBST(root->left);
        }
        bool right = true;
        if (root->right != nullptr) {
            right = root->val < root->right->val && isValidBST(root->right);
        }
        return left && right;
    }
};

解答错误。仅仅比较了节点与其左右子节点的大小关系。

解法 2：递归

左子树所有的节点都应该小于根节点，右子树的所有节点都应该大于根节点。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return traverse(root, LONG_MIN, LONG_MAX);
    }

    bool traverse(TreeNode* node, long min, long max) {
        if (node == nullptr) {
            return true;
        }
        if (node->val <= min || node->val >= max) {
            return false;
        } else {
            return traverse(node->left, min, node->val) && traverse(node->right, node->val, max);
        }
    }
};

当有节点值等于根节点值时也不是有效的二叉搜索树。还需要注意输入数值的取值范围，这里只能使用 long。

解法 3：中序遍历

当二叉搜索树中序遍历后，形成的序列应该为从小到大依次排列。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<long> v{};
        traverse(root, v);
        for (int i = 0; i < v.size() - 1; ++i) {
            if (v[i + 1] <= v[i]) {
                return false;
            }
        }
        return true;
    }

    void traverse(TreeNode* node, vector<long> &v) {
        if (node == nullptr) {
            return;
        }
        traverse(node->left, v);
        v.emplace_back(node->val);
        traverse(node->right, v);
    }
};

执行效率低。

653 两数之和 IV - 输入二叉搜索树

给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。

解法 1：遍历与哈希表

遍历树中元素并存入哈希表中，遍历哈希表检测是否有符合条件的两个元素。

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> set{};
        traverse(root, set);
        for (int x : set) {
            if (set.find(k - x) != set.end() && *set.find(k - x) != x) {
                return true;
            }
        }
        return false;
    }

    void traverse(TreeNode* node, unordered_set<int> &set) {
        if (node == nullptr) {
            return;
        }
        traverse(node->left, set);
        set.insert(node->val);
        traverse(node->right, set);
    }
};

注意需要排除找到的元素与自己相同的情况，比如输入 [1], 2。

解法 2：中序遍历与双指针

首先将二叉搜索树中序遍历转换为有序数组，再使用头尾两个指针查找是否有满足要求的两个元素。

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        vector<int> vector{};
        traverse(root, vector);
        int head = 0;
        int end = vector.size() - 1;
        while (head != end) {
            if (vector[head] + vector[end] > k) {
                end--;
            } else if (vector[head] + vector[end] < k) {
                head++;
            } else {
                return true;
            }
        }
        return false;
    }

    void traverse(TreeNode* node, vector<int> &v) {
        if (node == nullptr) {
            return;
        }
        traverse(node->left, v);
        v.emplace_back(node->val);
        traverse(node->right, v);
    }
};

235 二叉搜索树的最近公共祖先

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

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

解法 1：递归

从根节点开始，如果两个值都小于根节点，则将根节点设置为根节点的左节点进行递归，大于则设置为右节点。当前节点与左右节点中任意一个相同时或当前节点为 p、q 中间值则结束递归。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || p == nullptr || q == nullptr) {
            return nullptr;
        }
        if (p->val > q->val) {
            TreeNode* t = p;
            p = q;
            q = t;
        }
        if (root == p || root == q) {
            return root;
        }
        if (root->val > p->val && root->val < q->val) {
            return root;
        }
        if (p->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        }
        if (q->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        }
        return nullptr;
    }
};

解法 2：迭代

也可以从根节点开始迭代地往下查找。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || p == nullptr || q == nullptr) {
            return nullptr;
        }
        while (root != p && root != q && !(root->val < max(p->val, q->val) && root->val > min(p->val, q->val))) {
            if (root->val > max(p->val, q->val)) {
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return root;
    }
};

标签：return,入门,val,int,nullptr,节点,数据结构,root,LeetCode
From： https://www.cnblogs.com/futureknight/p/17233846.html