Leecode刷题心得和bug（哈希表和二叉树）
一、哈希表
0 哈希表基础知识
三种常见的哈希表
当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
- 数组
- set （集合）
- map(映射)
这里数组就没啥可说的了，我们来看一下set。
在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：
| 集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
| std::multiset | 红黑树 | 有序 | 是 | 否 | O(logn) | O(logn) |
| std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
| 映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(logn) | O(logn) |
| std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。
当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。
其他语言例如：java里的HashMap ，TreeMap 都是一样的原理。可以灵活贯通。
虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，但是std::set、std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。
242 有效的字母异位词
题目描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
解释：字母异位词就是两个字符串使用的字母种类和个数均相同，只是顺序不同
AC源码及注释
class Solution {
public:
bool isAnagram(string s, string t) {
//暴力解法，反而还很复杂，感觉逻辑还很绕，需要两个for循环
//上数哈希法，遍历s，在字母对应下标的元素值++；遍历t，在字母对应下标的元素值--
//若最后数组中全为0说明，s和t互为字母异位词
int record[26] = {0};
for (int i = 0; i < s.size(); i++) {
record[s[i] - 'a']++;
}
for (int i = 0; i < t.size(); i++) {
record[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (record[i] != 0) {
return false;
}
}
return true;
}
};
总结
- 本题核心就是先对某一字符串的字母种类及数量进行统计，涉及到统计某类数据数量的就是哈希表的应用场景
- 本题使用数组作为哈希表更为简单，因为事先知道数据种类的多少，可以开出定长的数组存放出现的字符数量
349 两个数组的交集
题目描述
给定两个数组，计算它们的交集
AC源码及注释
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//首先因为输出每个元素都是唯一的，所以用于输出的数据结构可以是set，因为插入时自动判重
unordered_set<int> result_set;
//数组哈希法
//由于给出了输入数组的数值范围，所以可以使用数组作为哈希表
// int hash[1005] = {0};
// for (int i = 0; i < nums1.size(); i++) {
// hash[nums1[i]] = 1;
// }
// for (int num : nums2) {
// if (hash[num] == 1) {
// result_set.insert(num);
// }
// }
// //有一个set的变量，转成vector的方法。
// return vector<int>(result_set.begin(), result_set.end());
//使用set
//此时numset里面是nums1数组去重后的元素，使用unordered_set其查找速度是常数
unordered_set<int> num_set(nums1.begin(),nums1.end());
//遍历nums2，若nums2的元素在numset中出现过则插入结果集
for (int num : nums2) {
//unorderedset用于查找元素的写法，很奇怪，官方解释是：
//如果找到指定元素，它返回元素的迭代器，如果找不到指定元素，则返回指向unordered_set::end()的迭代器。
if(num_set.find(num) != num_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
总结
- 无论是数组哈希还是set哈希，实际上都是用了两个哈希表：第一个set哈希存放结果集，第二个（数组/set）哈希存放第一个数组出现过的数字种类（数组就标记相应种类的下标的值为1/set直接存放数字就行，因为会自动去重）
- 学习在set中寻找某元素是否存在的写法
- 学习将set转成vector和使用vector初始化set的写法
202 快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
AC代码及注释
class Solution {
public:
bool isHappy(int n) {
//如果无限循环了，那么说明其中的一个sum重复出现了
//快速判断一个元素是否重复实现，使用哈希法了
unordered_set<int> result;
result.insert(n);
n = calSqrtSum(n);
while (n != 1) {
if (result.find(n) != result.end()) {
return false;
} else {
result.insert(n);
n = calSqrtSum(n);
}
}
return true;
}
int calSqrtSum(int n) {
int sum = 0;
while (n != 0) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
};
总结
- 重复计算快乐数和将结果插入set这两个操作，发现1出现或者重复值出现立即返回true或者fasle
1 两数之和
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
AC源码及注释
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//为什么使用哈希表？
//因为遍历到当前元素时，需要快速找到已遍历元素中是否存在符合条件的元素
//为什么考虑使用map？
//因为如果查找到符合条件的元素还需要能够知道元素在数组中的下标，key-value的数据结构符合条件
//因为是要查找是否存在元素，所以key存放元素值，value存放下标
unordered_map<int,int> map;
for (int i = 0; i < nums.size(); i++) {
//这里是定义一个迭代器来接收find的返回值
auto iter = map.find(target - nums[i]);
//迭代器等于end()就是没找到，不等于就是找到了
if (iter != map.end()) {
//需要返回已知个数大小的vector可以采用这种写法
return {iter->second, i};
}
//插入的语法
map.insert(pair<int, int>(nums[i], i));
}
//返回空的vector
return {};
}
};
总结
- 若能想到使用哈希表，那么这道题的思路还是很清晰的。遍历数组，查看target-当前value的结果是否存在于map中，若存在，则返回当前元素的下标和寻找到的结果的second值（value），也就是结果的下标。
- 那么这道题主要是关于map的很多操作，比如使用迭代器去map中寻找目标值，返回类型是vector时可以像👆一样return，在map中插入的语法等。
- 同时注意，要查找的内容放在key中。map: <key, value> == <first, second>
454 四数相加II
题目描述
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
例如:
输入:
- A = [ 1, 2]
- B = [-2,-1]
- C = [-1, 2]
- D = [ 0, 2]
输出:
2
解释:
两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
AC源码及注释
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
//太牛了，map统计nums1和nums2中各元素相加及其出现的次数
//在map中查找0-nums3元素-nums4元素出现的次数
unordered_map<int,int> map;
int record = 0;
for (int a : nums1) {
for (int b : nums2) {
map[a + b]++;
}
}
for (int c : nums3) {
for (int d : nums4) {
if (map.find(0 - (c + d)) != map.end()){
record += map[0- (c + d)];
}
}
}
return record;
}
};
总结
- 思路很牛，只有看到白纸黑字了才知道怎么回事。同时学习map的一种类数组的访问方式 value = map[key]
383 赎金信
题目描述
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意：
你可以假设两个字符串均只含有小写字母。
canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true
AC源码及注释
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
//看的是magazine中是否有组成ransomnote所有的字符
//record记录ransomnote中所需要的各种字符的个数
//遍历magazine，给予字符，对应值--
//如果存在值大于0，说明magazine没给够，就不行
int record[26] = {0};
for (int i = 0; i < ransomNote.size(); i++) {
record[ransomNote[i] - 'a']++;
}
for (int i = 0; i < magazine.size(); i++) {
record[magazine[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (record[i] > 0) {
return false;
}
}
return true;
}
};
总结
- 简单，没什么好说的
15 三数之和
题目描述
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
AC源码及注释
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//说的是哈希表很难，那就不看了
//又是牛逼的双指针
//从0开始遍历，设置i+1为left指针，设置末尾为right指针
//需要先将目标数组进行升序排序处理，方便后面指针的移动和边界条件以及去重
//判断nums[i]+nums[left]+nums[right]是否等于0，大于0就是right--；小于0就是left++
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
//若当前确定的a已经大于0了，说明后面都不会出现满足条件的三元组了
if (nums[i] > 0) {
return result;
}
//a去重的逻辑，当前值与前一个值比较
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] > 0) right--;
else if (nums[i] + nums[left] + nums[right] < 0) left++;
else {
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
//找到后，仍要继续操作：进行b和c的去重
//right就往前面一个比较
while (left < right && nums[right] == nums[right - 1]) right--;
//left就往后面一个比较
while (left < right && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
};
总结
- 总体就是一个排序+双指针的思路
18 四数之和
题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
AC源码及注释
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//思路和三数之和完全一样
//多了一层循环，外面两层for循环确定a和b，内部双指针确定c和d
//注意两层for循环的剪枝处理(与三数略有不同) 去重处理(基本一致)
//双指针是一样的
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
// 剪枝处理
if (nums[k] > target && nums[k] >= 0) {
break; // 这里使用break，统一通过最后的return返回
}
// 对nums[k]去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// 2级剪枝处理
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
// 对nums[i]去重
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
// nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
};
总结
- 自己再做一遍，还是卡住，在双层for循环上
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > target && nums[i] >= 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break;
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
无论是在剪枝还是去重上都与三数之和有所不同，在第一重循环的剪枝上，由于之前的target定了是0，但是现在target可能为负数，那么的话对于target = -2 nums = [-1, -1, 0, 0]就不符合了，就不能只因为nums[0] = -1比-2大就简单剪枝了，如果加上后面的负数是有可能等于target的，所以在剪枝上要求是非负数。第一重循环的去重与三数之和并无差异。
在第二重的剪枝和循环上都要注意应该在三数之和的基础上，比如说剪枝上要加上nums[i]再判断条件，去重上需要比自己的初值大等等
- 在四数相加的条件中有可能溢出，需要强制转换类型int->long
二、二叉树
513 找树左下角的值
题目描述
给定一个二叉树，在树的最后一行找到最左边的值。
AC源码及注释
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
//使用队列统计每一层，若计算到下一层节点个数为0说明，当前层是最后一层，取出第一个元素就是最左边的元素
//巴嘎的思路，层序遍历，然后额外记录一下第一个元素就行了，层序遍历完结束存的值就是需要的
queue<TreeNode*> que;
que.push(root);
int result = 0;
int size = 0;
while (!que.empty()) {
size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (i == 0) result = node->val;
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
//递归
class Solution {
public:
int maxDepth = INT_MIN;
int result;
void traversal(TreeNode* root, int depth) {
if (root->left == NULL && root->right == NULL) {
if (depth > maxDepth) {
maxDepth = depth;
result = root->val;
}
return;
}
if (root->left) {
depth++;
traversal(root->left, depth);
depth--; // 回溯
}
if (root->right) {
depth++;
traversal(root->right, depth);
depth--; // 回溯
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return result;
}
};
总结
- 用迭代法的思路就很清晰，在while中的for循环中，取出i == 0的节点就是一层最左边的节点。while循环结束后，result中的就是最后一层的最左边叶子
- 使用递归的话，核心思想就是优先左边搜索，同时记录深度最大的叶子结点，递归结束后就是题设所需答案。优先左边搜索在这道题前后中序都可以，因为没有中间节点的处理逻辑，即指存在左右节点的递归。在寻找最大深度的递归中需要回溯！
112 路径总和
题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
AC源码及注释
class Solution {
public:
//感觉自己的思路已经很接近题解了，感觉也不知道为什么会错
//题解是逆向思维，用targrtnum不断减去路径上节点的值，若当前叶子结点的count值等于0，那么就找到了
//我就是不断加啊看到叶子结点的值会不会等于targetnum
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
int sum = root->val;
return deepTraversal(root, sum, targetSum);
}
//用深度遍历哪个？有回溯那个吗
bool deepTraversal(TreeNode* root, int& sum, int targetSum) {
if (!root->left && !root->right && sum == targetSum) return true;
if (!root->left && !root->right) return false;
if (root->left) {
sum += root->left->val;
//这里super关键
if (deepTraversal(root->left, sum, targetSum)) return true;
sum -= root->left->val;
}
if (root->right) {
sum += root->right->val;
if (deepTraversal(root->left, sum, targetSum)) return true;
sum -= root->right->val;
}
return false;
}
// bool hasPathSum(TreeNode* root, int targetSum){
// if (!root) return false;
// return traversal(root, targetSum - root->val);
// }
// bool traversal(TreeNode* root, int count){
// if (!root->left && !root->right && count == 0) return true;
// if (!root->left && !root->right) return false;
// if (root->left) {
// count -= root->left->val;
// if (traversal(root->left, count)) return true;
// count += root->left->val;
// }
// if (root->right) {
// count -= root->right->val;
// if (traversal(root->right, count)) return true;
// count += root->right->val;
// }
// return false;
// }
};
总结
- 这道题的核心逻辑十分类似寻找最大深度的节点那道题，都涉及到了递归回溯的操作。在这类题中，回溯是最重要的部分。在题设中，随着函数递归调用的过程中，会存在我们需要操作的变量，即向下递归一层做某些操作，向上释放的时候做一些抵消性的操作。
- 在寻找最大深度节点的题中，depth变量的便是这样的一类变量。而在本题中，target减去根节点到当前节点路径和的变量count就是这类变量。
- 这类题还有一部分难点，就是在合适的地方return合适的值。首先我们应该充分考虑递归到终止时的各类操作。在本题中就是，递归到叶子结点终止，判断count是否等于0来决定终止子问题的返回值。
- 本题最重要的return地方就是利用子问题的返回值来确定子问题的父问题的返回值。若子问题返回值是1，那么父问题同样是1，这是一个向上传递的过程。
if (root->left) {
count -= root->left->val;
//here
if (traversal(root->left, count)) return true;
count += root->left->val;
}
if (root->right) {
count -= root->right->val;
//here
if (traversal(root->right, count)) return true;
count += root->right->val;
}
- 最后其他情况全都return false。
113 路径总和ii
题目描述
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
AC源码及注释
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if (!root) return result;
path.push_back(root->val);
traversal(root, targetSum - root->val);
return result;
}
void traversal(TreeNode* cur, int count){
if (!cur->left && !cur->right && count == 0) {
result.push_back(path);
}
if (!cur->left && !cur->right) return;
if (cur->left) {
path.push_back(cur->left->val);
count -= cur->left->val;
traversal(cur->left, count);
count += cur->left->val;
path.pop_back();
}
if (cur->right) {
path.push_back(cur->right->val);
count -= cur->right->val;
traversal(cur->right, count);
count += cur->right->val;
path.pop_back();
}
return;
}
};
总结
- 最开始就有思路，但是有几个问题我没想通，所以自己没写出来。我以为也像上一题一样，递归函数整一个bool类型，然后判断当前子问题返回值是1，然后再把节点压入栈。但是这样的话，就不清楚什么时候会递归释放回到根节点，然后把当前记录的path清零。
- 看了题解就恍然大悟！result和path设为全局变量。当递归到叶子结点时并发现满足条件，就把当前记录的path压入result中。同时在递归回溯的操作中增加了把当前节点值压入path的操作，每当进入一个问题时，path中都是对应的path。
- 然后就是栈的pop是pop_back().
106 从中序与后序遍历序列构造二叉树
题目描述
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树
AC代码及注释
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
//本题重点是模拟切割中序和后序数组
//这个题要疯吧
//你妈的啊
if (postorder.size() == 0) return NULL;
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorder.size() == 1) return root;
//什么鬼居然是这出错了
//我操啊就是把break跟flag = i写到一行了，if不打括号的话只能对紧跟着的后面一句代码生效
//相当于循环的第一轮判断条件后，马上就break退出循环了
// int flag;
// for (int i = 0; i < inorder.size(); i++) {
// if (inorder[i] == rootValue) flag = i; break;
// }
int flag;
for (flag = 0; flag < inorder.size(); flag++) {
if (inorder[flag] == rootValue) break;
}
vector<int> leftInorder(inorder.begin(), inorder.begin() + flag);
vector<int> rightInorder(inorder.begin() + flag + 1, inorder.end());
postorder.resize(postorder.size() - 1);
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = buildTree(leftInorder, leftPostorder);
root->right = buildTree(rightInorder, rightPostorder);
return root;
}
};
总结
- 这个题要把划分的递归树画出来就好看了，后面补上。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IpFAGImJ-1669890666693)(/Users/xuweijian/Studys/typora-notes/algo-notes/img/image-20221124151110400.png)]
- 救命啊，看注释里出的问题。
- 注意两道题对数组的划分都是左闭右开。右开就很方便，因为在for循环的就可以用end()的迭代器，指向尾元素的后一位或者是用size()作为标准。
- 这两道题递归时可以选择传数组也可以选择传入索引。这道题用的是传数组，下一题用的是传索引。关于这两种思路，笔记如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IWn9dltW-1669890666694)(/Users/xuweijian/Studys/typora-notes/algo-notes/img/image-20221124151402648.png)]
105 从前序与中序遍历序列构造二叉树
题目描述
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
AC源码及注释
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//这道题的解法采用下标索引作为参数传入，减少每次递归创建vector的开销。
//同时也避免了切割前序数组时，需要从最前方向后收缩的问题
//因为上一道题是提供后序数组，切割时需要把最后一个元素剔除，用一个resize减少数组大小即可
if (preorder.size() == 0 || inorder.size() == 0) return nullptr;
return traversal(preorder, inorder, 0, preorder.size(), 0, inorder.size());
}
TreeNode* traversal(vector<int>& preorder, vector<int>& inorder, int preBegin, int preEnd, int inBegin, int inEnd){
if (preBegin == preEnd) return nullptr;
int rootValue = preorder[preBegin];
TreeNode* root = new TreeNode(rootValue);
if (preEnd - preBegin == 1) return root;
int flag;
for (flag = inBegin; flag < inEnd; flag++) {
if (inorder[flag] == rootValue) break;
}
int leftInBegin = inBegin;
int leftInEnd = flag;
int leftPreBegin = preBegin + 1;
int leftPreEnd = leftPreBegin + (leftInEnd - leftInBegin);
root->left = traversal(preorder, inorder, leftPreBegin, leftPreEnd, leftInBegin, leftInEnd);
int rightInBegin = flag + 1;
int rightInEnd = inEnd;
int rightPreBegin = leftPreEnd;
int rightPreEnd = preEnd;
root->right = traversal(preorder, inorder, rightPreBegin, rightPreEnd, rightInBegin, rightInEnd);
return root;
}
};
总结
- 上道题基本上都总结了，两道题联系在一起看。
654 最大二叉树
题目描述
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
AC源码及注释
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if (nums.size() == 0) {
return nullptr;
}
return traversal(nums);
}
TreeNode* traversal(vector<int>& nums) {
if (nums.size() == 0) return nullptr;
int maxIndex = findMax(nums);
TreeNode* root = new TreeNode(nums[maxIndex]);
if (maxIndex == 0) root->left = nullptr;
else {
vector<int> left(nums.begin(), nums.begin() + maxIndex);
root->left = traversal(left);
}
if (maxIndex == nums.size() - 1) root->right = nullptr;
else {
vector<int> right(nums.begin() + maxIndex + 1, nums.end());
root->right = traversal(right);
}
return root;
}
int findMax(vector<int>& nums) {
int index = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > nums[index]) index = i;
}
return index;
}
};
总结：
- 感觉这道题和上面两道题都是一个套路，递归分割用于构造二叉树的数组然后构造二叉树。
- 这道题用的效率比较低下的传数组方式，同样可以采用传索引的方式。在这里的代码有优化的手段：
if (maxIndex == 0) root->left = nullptr;
else {
vector<int> left(nums.begin(), nums.begin() + maxIndex);
root->left = traversal(left);
}
if (maxIndex == nums.size() - 1) root->right = nullptr;
else {
vector<int> right(nums.begin() + maxIndex + 1, nums.end());
root->right = traversal(right);
}
在这里我想的是根据maxIndex位置的特殊性，如果在起始或末尾就不用递归构造子树了，然后直接给对应子树赋空值。但其实只要在非特殊位置构造相应子树即可，比如只要不在起始位置，就正常构造左子树；只要不在末尾，就正常构造右子树。可以不对特殊情况处理，因为在创建root节点时，左右子树已经被赋空值。
617 合并二叉树
题目描述
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
AC源码及注释
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (!root1 && !root2) return nullptr;
return traversal(root1, root2);
}
TreeNode* traversal(TreeNode* root1, TreeNode* root2) {
if (!root1 && !root2) {
return nullptr;
}
if (root1 && !root2) {
return root1;
} else if (!root1 && root2) {
return root2;
}
TreeNode* root = new TreeNode(root1->val + root2->val);
root->left = traversal(root1->left, root2->left);
root->right = traversal(root1->right, root2->right);
return root;
}
};
总结
- 这道题很奇怪的，做起来还是跟前三道题一个套路，但是自己还是一开始没做出来。自己做的时候就是想完全建一颗新树，如果传入的两个节点都是空，那么直接返回空。然后if逻辑判断新建节点的节点值用于新建节点，然后再递归确定新建节点的左右孩子，但是第一次报错：在递归得到左孩子那一行报访问空指针的错。
- 然后尝试直接在if逻辑计算节点值的时候，就新建好节点返回。这样不报错了，同时给的几个样例也过了。但是提交有一个样例过不了
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ydBoQeZK-1669890666694)(/Users/xuweijian/Studys/typora-notes/algo-notes/img/image-20221125152930341.png)]
其实我也不是很理解这棵树怎么建的，可能是因为节点对不上？
- 最后还是模仿的题解，在if逻辑中直接返回现成的root1和root2节点，然后最后返回相加后的节点还是采用新建节点的做法就过了。真的好奇怪，这道题就全部用现成的节点就是最保险的，也不会额外占用内存。
98 验证二叉搜索树
题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
AC源码及注释
class Solution {
public:
bool isValidBST(TreeNode* root) {
traversal(root);
if (vec.size() == 0) return true;
for (int i = 0; i < vec.size() - 1; i++) {
if (vec[i] >= vec[i + 1]) return false;
}
return true;
}
vector<int> vec;
void traversal(TreeNode* root) {
//左右子树都是二叉搜索树，根节点也是满足大于左孩子小于右孩子，直接组合起来不一定是二叉搜索树
// if (root->left && root->left->val >= root->val) return false;
// if (root->right && root->right->val <= root->val) return false;
// bool leftTraversal = true;
// bool rightTraversal = true;
// if (root->left) leftTraversal = traversal(root->left);
// if (root->right) rightTraversal = traversal(root->right);
// return leftTraversal && rightTraversal;
//利用二叉搜索树中序序列是递增的特性
if (!root) return;
traversal(root->left);
vec.push_back(root->val);
traversal(root->right);
}
};
总结
- 如注释所示，使用递归有一个误区，这道题不能简单地把问题拆成子问题求解。
- 巧妙的思路：有效的二叉搜索树 == 中序序列递增无重复。
700 二叉搜索树中的搜索
题目描述
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
AC源码及注释
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (!root) return nullptr;
return traversal(root, val);
}
TreeNode* traversal(TreeNode* root, int val) {
if (root->val == val) return root;
//注意谁比谁大啊
if (val < root->val) {
if (root->left) return traversal(root->left, val);
else return nullptr;
} else {
if (root->right) return traversal(root->right, val);
else return nullptr;
}
}
};
总结
- 本题就属于递归和迭代都相当简单的那类题。
530 二叉搜索树的最小绝对差
题目描述
给你一个二叉搜索树的根节点
root，返回 树中任意两不同节点值之间的最小差值 。差值是一个正数，其数值等于两值之差的绝对值。
AC源码及注释
class Solution {
public:
vector<int> vec;
void treeToArr(TreeNode* root) {
if (!root) return;
treeToArr(root->left);
vec.push_back(root->val);
treeToArr(root->right);
}
int getMinimumDifference(TreeNode* root) {
//二叉搜索树中序遍历可以转成有序数组是最大的特性
treeToArr(root);
if (vec.size() < 2) return 0;
int min = INT_MAX;
for (int i = 1; i < vec.size(); i++) {
if (vec[i] - vec[i - 1] < min) min = vec[i] - vec[i - 1];
}
return min;
}
};
总结
501 二叉搜索树中的众数
题目描述
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
AC源码及注释
class Solution {
public:
//虽然是简单题，但是真的好牛。这道题根据是不是二叉搜索树的思路其实是不同的
//非二叉搜索树，遍历完整棵树，将每种元素的出现频率都记录到map中，然后将map转成vector数组，定义cmp函数后传入sort就可以对数组按照出现频率来进行排序。取出最高频的几个元素即可。
//二叉搜索树因为等价于有序数组，相同的元素一定是紧挨着的。但是正常思维下也是需要遍历两遍数组或者树。通过定义当前节点cur的前一个节点pre，比较cur和pre就可以知道该种元素的出现频率。当出现频率等于最大频率时，加入该元素到result中；当不相等的时候，更新最大频率同时清空result数组。
int count = 0;
int maxCount = 0;
TreeNode* pre =nullptr;
vector<int> result;
void traversal(TreeNode* cur) {
if (!cur) return;
traversal(cur->left);
if (!pre) {
count = 1;
} else if (pre && pre->val == cur->val) {
count++;
} else {
count = 1;
}
pre = cur;
if (count > maxCount) {
maxCount = count;
result.clear();
result.push_back(cur->val);
} else if (count == maxCount) {
result.push_back(cur->val);
}
traversal(cur->right);
return;
}
vector<int> findMode(TreeNode* root) {
traversal(root);
return result;
}
};
总结
236 二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
AC源码及注释
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == p || root == q || root == NULL) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p ,q);
if (left && right) return root;
if (!left && right) return right;
else if (left && !right) return left;
else return NULL;
}
};
总结
- 自己总结就是不如直接看卡哥的题解
235 二叉搜索树的最近公共祖先
题目描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
AC源码及注释
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//有序搜索树的特性：从上往下遍历，只要第一次遇到一个节点的值在[p->val, q->val]中
//这个节点就一定是p和q的最近公共节点
if (!root) return NULL;
if (root->val > p->val && root->val > q->val) {
TreeNode* left = lowestCommonAncestor(root->left, p, q);
if (left) return left;
}
if (root->val < p->val && root->val < q->val) {
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (right) return right;
}
return root;
}
};
总结
- 自己第一遍看了思路还是没写对。看注释的思路，很容易让人先写出判断是否在pq之间的逻辑然后返回root的操作，然后直接左右孩子递归。但是例子都过不了，其实没想通，对比题解后难道是因为直接左右孩子递归是遍历了整棵树，只遍历边就不会错？
- 其次注意并没有规定p的值一定就小于q的值。
701 二叉搜索树中的插入操作
题目描述
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
AC源码及注释
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
TreeNode* node = new TreeNode(val);
if (!root) return node;
TreeNode* cur = root;
while (1) {
if (cur->val > val && cur->left) {
cur = cur->left;
} else if (cur->val < val && cur->right) {
cur = cur->right;
} else if (cur->val > val && !cur->left) {
cur->left = node;
break;
} else {
cur->right = node;
break;
}
}
return root;
}
};
总结
- 简单，直接迭代就行了，注意题设是二叉搜索树去思考如何它的特性。
450 删除二叉搜索树的节点
题目描述
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
AC源码及注释
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
//其实可以不写递归，就先寻找节点
//找到了就进行删除操作，找不到就直接返回root
//先写一次不递归的代码
// TreeNode* cur = root;
// TreeNode* parent = root;
// while (!cur) {
// if (cur->left && cur->val > key) {
// parent = cur;
// cur = cur->left;
// }
// if (cur->right && cur->val < key) {
// parent = cur;
// cur = cur->right;
// }
// if (cur->val == key) break;
// }
// if (!cur) return root;
// if (!cur->left && !cur->right) {
// delete cur;
// return root;
// } else if (!cur->left) {
// //啊啊写不下去了
// //就算是记录了父节点，也不知道cur是父节点的什么孩子，还得要一个变量来记录。直接抄递归吧。
// }
if (!root) return root;
if (root->val == key) {
if (!root->left && !root->right) {
delete root;
return nullptr;
}
else if (!root->left) {
auto retNode = root->right;
delete root;
return retNode;
}
else if (!root->right) {
auto retNode = root->left;
delete root;
return retNode;
}
else {
TreeNode* cur = root->right;
while (cur->left) {
cur = cur->left;
}
cur->left = root->left;
TreeNode* tmp = root;
root = root->right;
delete tmp;
return root;
}
}
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
}
};
总结
- 在二叉搜索树删除节点的操作，主要是需要考虑的情况较多，在最后一种情况删除节点的左右孩子均存在的情况下，需要做出比较特殊的操作，需要画图理解，如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EXJ42UcE-1669890666695)(/Users/xuweijian/Studys/typora-notes/algo-notes/img/image-20221129115901934.png)]
- 在最开始的想要直接找到需要删除的节点，然后进行操作的思路，应该是可行的，但需要额外记录父节点以及删除节点是父节点的哪个孩子，不如直接递归。
669 修建二叉搜索树
1.题目描述
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
2.AC源码及注释
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
//最开始我的思路是，找到不符合在区间的节点调用上道题的删除节点函数
//但是删除了一个节点后，怎么继续遍历树去删有点理不清楚逻辑
//而且这道题特殊的是，如果这个节点是在区间左边的，那么这个节点的左孩子及以下都不在啊
//而是把这个节点的右孩子返回
if (!root) return root;
if (root->val < low) {
//不管是第一次写的可以把root节点delete掉后return孩子
//还是直接return孩子，这都是终止条件里的逻辑，执行过后就不会再往后递归了
//如果遇到了孩子也不符合的情况就不行了
// TreeNode* tmp = root;
// root = root->right;
// delete tmp;
//return root;
//return root->right;
TreeNode* right = trimBST(root->right, low, high);
return right;
}
if (root->val > high) {
// TreeNode* tmp = root;
// root = root->left;
// delete tmp;
//return root;
//return root->left;
TreeNode* left = trimBST(root->left, low, high);
return left;
}
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
3.总结
总结都在注释里了
108 将有序数组转换成二叉搜索树
1.题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
2.AC源码及注释
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) {
return nullptr;
}
return traversal(nums, 0, nums.size() - 1);
}
TreeNode* traversal(vector<int> nums, int left, int right) {
if (left == right) {
TreeNode* node = new TreeNode(nums[left]);
return node;
}
int mid = (right - left) / 2 + left;
TreeNode* node = new TreeNode(nums[mid]);
if (mid == left) {
node->left = nullptr;
node->right = traversal(nums, mid + 1, right);
return node;
}
node->left = traversal(nums, left, mid - 1);
node->right = traversal(nums, mid + 1, right);
return node;
}
};
3.总结
- 找到区间的中间值新建节点，然后递归到左右区间。
- 在我的题解中在偶数个数的区间中设置的左边元素作为中间节点，所以可能会遇到一种情况，就是找到的中间节点已经是区间的最左值，此时中间节点的左孩子直接设置为空即可。
538 把二叉搜索树转换为累加
1.题目描述
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。文章来源地址https://www.toymoban.com/news/detail-441868.html
2.AC源码及注释
class Solution {
public:
int pre = 0;
void traversal(TreeNode* cur){
if (!cur) return;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);
}
TreeNode* convertBST(TreeNode* root) {
//开始没看懂题意，首先把二叉搜索树看成一个数组。
//比如[1,2,3,4]从后往前逐个累加变换成[10,9,7,4]，把对应的节点变换成累加后的值。
if (!root) return nullptr;
traversal(root);
return root;
}
};
3.总结
- 关于题意的理解看注释。
- 这个过程就是从最右边的节点开始累加，以右中左的遍历顺序进行，所以只需要写出逆中序遍历的的逻辑。对中节点的处理逻辑就是，在当前节点值的基础上加上遍历的上一个节点值。
释文章来源：https://www.toymoban.com/news/detail-441868.html
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) {
return nullptr;
}
return traversal(nums, 0, nums.size() - 1);
}
TreeNode* traversal(vector<int> nums, int left, int right) {
if (left == right) {
TreeNode* node = new TreeNode(nums[left]);
return node;
}
int mid = (right - left) / 2 + left;
TreeNode* node = new TreeNode(nums[mid]);
if (mid == left) {
node->left = nullptr;
node->right = traversal(nums, mid + 1, right);
return node;
}
node->left = traversal(nums, left, mid - 1);
node->right = traversal(nums, mid + 1, right);
return node;
}
};
3.总结
- 找到区间的中间值新建节点，然后递归到左右区间。
- 在我的题解中在偶数个数的区间中设置的左边元素作为中间节点，所以可能会遇到一种情况，就是找到的中间节点已经是区间的最左值，此时中间节点的左孩子直接设置为空即可。
538 把二叉搜索树转换为累加
1.题目描述
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
2.AC源码及注释
class Solution {
public:
int pre = 0;
void traversal(TreeNode* cur){
if (!cur) return;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);
}
TreeNode* convertBST(TreeNode* root) {
//开始没看懂题意，首先把二叉搜索树看成一个数组。
//比如[1,2,3,4]从后往前逐个累加变换成[10,9,7,4]，把对应的节点变换成累加后的值。
if (!root) return nullptr;
traversal(root);
return root;
}
};
3.总结
- 关于题意的理解看注释。
- 这个过程就是从最右边的节点开始累加，以右中左的遍历顺序进行，所以只需要写出逆中序遍历的的逻辑。对中节点的处理逻辑就是，在当前节点值的基础上加上遍历的上一个节点值。
到了这里，关于Leecode刷题心得和bug（哈希表与二叉树）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[数据结构] 树与二叉树](https://imgs.yssmx.com/Uploads/2024/03/837706-1.png)
