二叉树收尾+回溯专题训练一
5/17
T90 子集二
1、昨天刚记录下的关于“存在重复情况该如何解决”的疑惑，在此题中便得到实战。由于本题数目较小，可以考虑延用上题做法，返回结果前去重即可。
2、相关代码如下：
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
//先排序，保证相同元素相邻
//否则例如 [1,2] 和 [2,1] 会被认为不同
sort(nums.begin(), nums.end());
//由于存在重复元素
//二进制枚举后可能出现重复子集
//因此用set自动去重
set<vector<int>> st;
int n = nums.size();
//总共有 2^n 个子集
//每一位表示当前元素取或不取
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> path;
//检查每一位
for (int i = 0; i < n; i++) {
//这一位为1，说明取当前元素
if (mask & (1 << i)) {
path.push_back(nums[i]);
}
}
//加入set自动去重
st.insert(path);
}
vector<vector<int>> result;
//转回vector
for (auto x : st) {
result.push_back(x);
}
return result;
}
};
注意：这里需要先排序再用去重，因为CPP官方库中集合的去重逻辑需要我们做如下处理。
3、优化解法待补充
备忘：Next数组 字符串复杂算法 哈希冲突
5/16
T78 子集
1、这一题也可以暴力解决，因为本质都需要遍历得到所有可能的集合。但是，与我一开始设想的逐位右移遍历不同，可以有很简单的写法。核心：利用题干中每个元素不同的特性【假设存在相同数，如何处理？】，子集本质为每个元素取或不取——对应0到2的n次方这些数的二进制表示，0-不取，1-取。代码如下：
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
int n = nums.size();
//总共有 2^n 个子集
//每一位表示当前元素选/不选
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> path;
//检查每一位
for (int i = 0; i < n; i++) {
//这一位为1，说明选当前元素
if (mask & (1 << i)) {
path.push_back(nums[i]);
}
}
result.push_back(path);
}
return result;
}
};
2、语法复习：
1 << n
表示 2^n
if (mask & (1 << i))
含义是：检查 mask 的第 i 位是不是 1
3、更优解（回溯写法）：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
if (startIndex >= nums.size()) { // 终止条件可以不加
return;
}
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};
（待debug模式手操）
T93 复原IP地址
1、这一题我直接用暴力for循环写的，剪枝则用最终长度是否匹配字符串本身长度来处理，耗时竟然是leetcode最快的方法之一。看来回溯法的确在时间上没有突破性优势，能用易理解方式解决的问题不必强行套回溯。这种方法的存在让题目不应该被打上“中等难度”标签，但面试官逼你写回溯的话的确有一定难度，后续需掌握多种解法。
class Solution {
public:
//判断一个字段是否合法
bool isValid(string str) {
//空字符串
if (str.size() == 0) return false;
//前导0
if (str.size() > 1 && str[0] == '0') return false;
int num = stoi(str);
//范围必须在0~255
if (num < 0 || num > 255) return false;
return true;
}
vector<string> restoreIpAddresses(string s) {
vector<string> result;
//如果s长度小于4或大于12，返回空
if (s.size() < 4 || s.size() > 12) {
return result;
}
//每个位置可能的数字长度为1/2/3
//按照第一个位置长度为1、2、3
for (int len1 = 1; len1 <= 3; len1++) {
//第二个长度为1、2、3
for (int len2 = 1; len2 <= 3; len2++) {
//第三个....
for (int len3 = 1; len3 <= 3; len3++) {
//第四个....
for (int len4 = 1; len4 <= 3; len4++) {
//四层for循环来遍历所有结果存储，长度不合理的剪枝跳过
if (len1 + len2 + len3 + len4 != s.size()) {
continue;
}
string a = s.substr(0, len1);
string b = s.substr(len1, len2);
string c = s.substr(len1 + len2, len3);
string d = s.substr(len1 + len2 + len3, len4);
//最后结果遍历一遍，不符合题干有效IP的过滤掉
if (isValid(a) &&
isValid(b) &&
isValid(c) &&
isValid(d)) {
result.push_back(
a + "." + b + "." + c + "." + d
);
}
}
}
}
}
return result;
}
};
2、这一题用回溯的话代码如下：
class Solution {
private:
vector<string> result;// 记录结果
// startIndex: 搜索的起始位置，pointNum:添加逗点的数量
void backtracking(string& s, int startIndex, int pointNum) {
if (pointNum == 3) { // 逗点数量为3时，分隔结束
// 判断第四段子字符串是否合法，如果合法就放进result中
if (isValid(s, startIndex, s.size() - 1)) {
result.push_back(s);
}
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
pointNum++;
backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
pointNum--; // 回溯
s.erase(s.begin() + i + 1); // 回溯删掉逗点
} else break; // 不合法，直接结束本层循环
}
}
// 判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
}
if (s[start] == '0' && start != end) { // 0开头的数字不合法
return false;
}
int num = 0;
for (int i = start; i <= end; i++) {
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
return false;
}
num = num * 10 + (s[i] - '0');
if (num > 255) { // 如果大于255了不合法
return false;
}
}
return true;
}
public:
vector<string> restoreIpAddresses(string s) {
result.clear();
if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
backtracking(s, 0, 0);
return result;
}
};
5/15
T131 分割回文串
1、这一题对比之前的组合，一个是选数字，一个是选切割位置： 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个….. 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段….. 但是，由于切割会将后序可选项细分为许多子集，看起来难一些
2、本题测试数据量较小，可以无需优化判断回文串的算法，代码随想录里的优化方式为动态规划，后续专题中再予以强调。
3、代码如下：
class Solution {
private:
vector<vector<string>> result;
vector<string> path; // 放已经回文的子串
void backtracking (const string& s, int startIndex) {
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isPalindrome(s, startIndex, i)) { // 是回文子串
// 获取[startIndex,i]在s中的子串
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else { // 不是回文，跳过
continue;
}
backtracking(s, i + 1); // 寻找i+1为起始位置的子串
path.pop_back(); // 回溯过程，弹出本次已经添加的子串
}
}
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};
5/14
T216 组合总和三
类似上一题，这里回溯框架和剪枝就有点像二叉树里递归框架+中间处理一样，是大套路中的小套路，风格比较统一。
class Solution {
private:
vector<vector<int>> result; // 存放结果集
vector<int> path; // 符合条件的结果
void backtracking(int targetSum, int k, int sum, int startIndex) {
if (sum > targetSum) { // 剪枝操作
return;
}
if (path.size() == k) {
if (sum == targetSum) result.push_back(path);
return; // 如果path.size() == k 但sum != targetSum 直接返回
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
sum += i; // 处理
path.push_back(i); // 处理
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i; // 回溯
path.pop_back(); // 回溯
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
result.clear(); // 可以不加
path.clear(); // 可以不加
backtracking(n, k, 0, 1);
return result;
}
};
上一题的组合优化方式（摘录）
剪枝优化
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。 注意代码中i，就是for循环里选择的起始位置。
for (int i = startIndex; i <= n; i++) {
优化过程如下： 已经选择的元素个数：path.size(); 所需需要的元素个数为: k - path.size(); 列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()） 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历 为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。 举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。 从2开始搜索都是合理的，可以是组合[2, 3, 4]。 这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。 所以优化之后的for循环是：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
优化后整体代码如下：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
path.push_back(i); // 处理节点
backtracking(n, k, i + 1);
path.pop_back(); // 回溯，撤销处理的节点
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
时间复杂度: O(n * 2^n) 空间复杂度: O(n)
5/13
【进入回溯专题】
【理论学习（摘抄自《代码随想录》】
什么是回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。 回溯是递归的副产品，只要有递归就会有回溯。 所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。
回溯法的效率
回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。 因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。 那么既然回溯法并不高效为什么还要用它呢？ 因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。 此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。
回溯法解决的问题
回溯法，一般可以解决如下几种问题： 组合问题：N个数里面按一定规则找出k个数的集合 切割问题：一个字符串按一定规则有几种切割方式 子集问题：一个N个数的集合里有多少符合条件的子集 排列问题：N个数按一定规则全排列，有几种排列方式 棋盘问题：N皇后，解数独等等 相信大家看着这些之后会发现，每个问题，都不简单！ 另外，会有一些同学可能分不清什么是组合，什么是排列？ 组合是不强调元素顺序的，排列是强调元素顺序。 例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。 记住组合无序，排列有序，就可以了。
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！ 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。 递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。 这块可能初学者还不太理解，后面的回溯算法解决的所有题目中，我都会强调这一点并画图举相应的例子，现在有一个印象就行。
回溯法模板
这里给出Carl总结的回溯算法模板。 在讲二叉树的递归 (opens new window) 中我们说了递归三部曲，这里我再给大家列出回溯三部曲。
回溯函数模板返回值以及参数
在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。 回溯算法中函数返回值一般为void。 再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。 但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。 回溯函数伪代码如下：
void backtracking(参数)
回溯函数终止条件
既然是树形结构，那么我们在讲解二叉树的递归 (opens new window) 的时候，就知道遍历树形结构一定要有终止条件。 所以回溯也有要终止条件。 什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。 所以回溯函数终止条件伪代码如下：
if (终止条件) {
存放结果;
return;
}
T77 组合
这一个专题的风格明显不太一样。例如本题，光看思路很简单：既然要输出所有结果，肯定得遍历，那就没有传统意义上的优化空间了。但是，不同遍历方式的复杂度、bug易发度还是有区别的。本题回溯写法如下：
class Solution {
public:
vector<vector<int>> res; // 存储所有结果
vector<int> path; // 当前组合
void backtracking(int n, int k, int startIndex) {
// 终止条件：当前组合长度等于 k
if (path.size() == k) {
res.push_back(path);
return;
}
// 从 startIndex 开始选择数字
for (int i = startIndex; i <= n; i++) {
path.push_back(i); // 选择当前数字
backtracking(n, k, i + 1); // 递归选择下一个数字
path.pop_back(); // 回溯，撤销选择
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return res;
}
};
【待完成】用debug模式从头到位跑一遍，再尝试不同方法
5/12
T538 把二叉搜索树转换为累加树
1、思路很直观： //先中序遍历做成有序数组 //让有序数组二维，另一维的值为大于当前值的累加和（遍历一次数组就能赋值） //遍历这棵树，根据当前值找到对应的greater sum，累加，更新节点值
代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> nums;
// 原值 -> greater sum
unordered_map<int, int> mp;
TreeNode* convertBST(TreeNode* root) {
// 中序遍历得到升序数组
inorder(root);
// 从后往前累加
int sum = 0;
for (int i = nums.size() - 1; i >= 0; i--) {
sum += nums[i];
// 当前值对应的新值
mp[nums[i]] = sum;
}
// 再遍历树，更新节点值
update(root);
return root;
}
// 中序遍历
void inorder(TreeNode* root) {
if (root == nullptr) return;
inorder(root->left);
nums.push_back(root->val);
inorder(root->right);
}
// 更新节点值
void update(TreeNode* root) {
if (root == nullptr) return;
root->val = mp[root->val];
update(root->left);
update(root->right);
}
};
2、但上面那种做法很慢，空间占用也较大。最优解：反中序：右中左 -> 从大到小，这样就可以维护一个累加和，每次遍历到新节点直接更新累加和并赋值节点新value即可。 代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
traverse(root);
return root;
}
void traverse(TreeNode* root) {
if (root == nullptr) return;
// 先遍历更大的节点
traverse(root->right);
// sum 中已经包含所有更大的值
sum += root->val;
// 更新当前节点
root->val = sum;
// 再遍历更小的节点
traverse(root->left);
}
};
注意：这里的几行代码顺序不能调换，必须先在更大的群组中更新sum，再更新root和sum，此时的sum才符合更小群组的先置要求
T108 将有序数组转为二叉搜索树
1、这一题要求为平衡二叉搜索树，我的直观想法是既然数组有序，直接每次取中间值，尽量做到平衡： //每次找数组中间的值作为当前节点，递归获取左右子节点 //这样每次左右子树的总节点数目最多只差一个 此时没有严格的数学证明，但代码可以高效AC：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
TreeNode* build(vector<int>& nums, int left, int right) {
// 区间为空，返回空节点
if (left > right) return nullptr;
// 取中间位置作为当前根节点
// 这样左右子树节点数尽量均衡
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
// 左半部分构造左子树
root->left = build(nums, left, mid - 1);
// 右半部分构造右子树
root->right = build(nums, mid + 1, right);
return root;
}
};
2、找到了正确性的数学证明，在力扣另一道题的官方题解中：https://leetcode.cn/problems/balance-a-binary-search-tree/solutions/241897/jiang-er-cha-sou-suo-shu-bian-ping-heng-by-leetcod/
这个证明的本质：我们构造树的核心逻辑和二分法很像，树的高度直观上就和一段数组能被2分的次数线形相关，因此用log2、指数做一些开闭的理论推导即可。简单理解就是稍微多一个节点不会让二分次数加超过一。
5/11
T669 修剪二叉搜索树
1、这一题我一开始的思路如下，是按照中序遍历二叉树特征+双向链表的想法写的： //层序遍历，让节点之间存在双向箭头 //中序遍历，分别找到低于和高于的节点群组 //对于每个需要修剪的节点，假如没有子节点，让它父亲的指针指向null（通过数值区分是左还是右节点） //对于有子节点的需要修剪的节点，子子节点的父节点、父节点的子节点改变 //删除null的指向，变成单向树 //无需考虑有待修剪子树有两个孩子的情况，因为有一侧肯定要全部删除 实际上，无需分组，直接递归遍历中比较大小即可：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<TreeNode*, TreeNode*> father;
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) return nullptr;
// 层序遍历，让节点之间存在“双向箭头”
queue<TreeNode*> que;
que.push(root);
father[root] = nullptr;
while (!que.empty()) {
TreeNode* cur = que.front();
que.pop();
if (cur->left) {
father[cur->left] = cur;
que.push(cur->left);
}
if (cur->right) {
father[cur->right] = cur;
que.push(cur->right);
}
}
// 从当前根节点开始修剪
root = trim(root, low, high);
return root;
}
TreeNode* trim(TreeNode* node, int low, int high) {
if (node == nullptr) return nullptr;
// 当前节点太小
// node 和 node 的左子树都要删除
// 只有 node->right 可能保留
if (node->val < low) {
TreeNode* p = father[node];
TreeNode* child = node->right;
if (child) father[child] = p;
if (p) {
if (p->left == node) p->left = child;
else if (p->right == node) p->right = child;
}
return trim(child, low, high);
}
// 当前节点太大
// node 和 node 的右子树都要删除
// 只有 node->left 可能保留
if (node->val > high) {
TreeNode* p = father[node];
TreeNode* child = node->left;
if (child) father[child] = p;
if (p) {
if (p->left == node) p->left = child;
else if (p->right == node) p->right = child;
}
return trim(child, low, high);
}
// 当前节点合法，继续修剪左右子树
node->left = trim(node->left, low, high);
if (node->left) father[node->left] = node;
node->right = trim(node->right, low, high);
if (node->right) father[node->right] = node;
return node;
}
};
2、然而，上述方法非常慢且代码冗长，容易出错，最优解思路如下：核心还是方法一的最后一行注释：小于最小的全部删除，大于最大的全部删除，不确定的继续递归。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) return nullptr;
// 当前节点太小：
// 因为是 BST，所以 root 的左子树一定全部 <= root->val，
// 因此 root 和它的左子树都不可能保留。
if (root->val < low) {
return trimBST(root->right, low, high);
}
// 当前节点太大：
// 因为是 BST，所以 root 的右子树一定全部 >= root->val，
// 因此 root 和它的右子树都不可能保留。
if (root->val > high) {
return trimBST(root->left, low, high);
}
// 当前节点在 [low, high] 范围内，可以保留。
// 但它的左右子树中仍可能有不合法节点，所以继续修剪。
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
教训：不要上来就想复杂，二叉树大部份题目还是可以简单递归秒掉，也不要因为有中序遍历有序这一特征就看到比大小就往上面凑，那会限制思路。