【算法专题】穷举vs暴搜vs深搜vs回溯vs剪枝
二叉树剪枝
LCR 047. 二叉树剪枝 - 力扣（LeetCode）
本题要求我们将全部为0的二叉树去掉，也就是剪枝，当我们举一个具体的例子进行模拟时，会发现，只关注于对其中一个子树的根节点进行剪枝，由于我们只去掉所有节点都是0的子树，所以需要先判断它的左子树是否被去掉，右子树是否被去掉，最后再判断根节点本身的值是否为0，如果这三个条件全部满足，我们需要告诉这个子树的父亲，该子树被去掉了。
通过上面的分析，不难发现，这个递归函数的传入参数只需要一个根节点的指针，并且该函数需要把剪枝的结果传给父亲，所以递归函数需要一个返回值。
/**
* 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* pruneTree(TreeNode* root)
{
if(root == nullptr) return nullptr;
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
if(root->left == nullptr && root->right == nullptr && root->val == 0)
{
delete root;
root = nullptr;
}
return root;
}
};验证二叉搜索树
98. 验证二叉搜索树 - 力扣（LeetCode）
关于二叉搜索树，有一个简单的性质就是：二叉搜索树的中序遍历序列是有序的。所以我们可以根据这个性质来验证一个二叉树是否为二叉搜索树，当然我指的并不是创建一个数组进行判断，而是递归实现二叉树的中序遍历，并在这个过程中去判断是否满足性质。
我们之所以要根据中序遍历序列来判断而不是简单地递归判断左节点小于根节点小于右节点是因为满足这个性质的不一定是二叉搜索树：
说回正题，那我们要怎么确定二叉树的中序遍历序列呢？实际上我们可以定义一个全局变量prev来充当遍历的“指针”，那么中序遍历过程中，我们只需要满足根节点的值大于prev，就能确保满足二叉搜索树的性质。
目前的思路已经能够完成这道题目了，但是我们现在就相当于老老实实地把整个二叉树遍历一遍，返回结果。但是只要我们发现左子树或者中间节点不符合二叉搜索树性质，就可以直接返回结果了，因为这注定不可能是二叉搜索树了。而这个操作，其实就是剪枝。
class Solution {
public:
long prev = LONG_MIN;
bool isValidBST(TreeNode* root)
{
if(root == nullptr) return true;
// 判断左子树是否满足二叉搜索树性质
bool left = isValidBST(root->left);
if(!left) return false; // 剪枝
// 判断当前节点是否满足性质
bool cur = false;
if(root->val > prev)
cur = true;
if(!cur) return false; // 剪枝
// 更新prev值
prev = root->val;
// 判断右子树是否满足二叉搜索树性质
bool right = isValidBST(root->right);
return left && right && cur;
}
};二叉树的所有路径
257. 二叉树的所有路径 - 力扣（LeetCode）
依据题意，我们需要把二叉树的所有从根节点到叶子节点的路径找出来，这显然就是个深度优先遍历问题（dfs），因为存在这样的情况：遍历到左边的叶子节点后，得到一个字符串后，进行回溯，再遍历右边的叶子节点，得到另一个字符串。所以我们需要想办法能对字符串进行回溯。
我们举一两个例子进行模拟就能发现，遍历二叉树的方式应为前序遍历，也就是先将根节点的值加入字符串，然后分别处理左子树和右子树。因为我们需要返回所有得到的字符串，所以可以定义一个全局的字符串数组，又因为我们需要得到从根节点到叶子的路径，所以递归函数还需要传入当前已经遍历的路径。
至于前面提到的回溯，其实只要递归函数传字符串的值而不是引用就行了，这样的话，遍历完左子树，将左子树的路径加入字符串数组，由于不改变已经遍历的路径，再去遍历右子树，就相当于实现了回溯。
class Solution {
public:
vector<string> ret;
void dfs(TreeNode* root, string path)
{
if(root->left == nullptr && root->right == nullptr)
{
path += to_string(root->val);
ret.push_back(path);
return;
}
path += to_string(root->val) + "->";
if(root->left) dfs(root->left, path);
if(root->right) dfs(root->right, path);
}
vector<string> binaryTreePaths(TreeNode* root)
{
string path;
dfs(root, path);
return ret;
}
};全排列
46. 全排列 - 力扣（LeetCode）
对于这种枚举类型的题目，我们首先要做的就是画出决策树，然后根据决策树进行递归代码的编写。题目要求我们返回所有满足条件的数组，我们如果让递归函数来传这些变量，不但存在开销，代码编写也会变得复杂，所以可以直接定义全局变量，省去考虑各种情况的麻烦。
关于全局变量的定义，首先肯定是一个二维数组ret，存所有排列的可能情况；又因为枚举过程中我们可能需要经常进行回溯，所以把存放排列顺序的数组path也定义为全局变量；最后，因为我们的决策树需要进行剪枝，所以为了方便判断是否剪枝，可以再定义bool类型的数组check，表示当前访问的节点是否已经被遍历。
递归函数的编写我们只需要考虑当前节点要干什么：遍历check数组判断是否遍历各子树，如果需要遍历，则将子节点值添加到path数组，将当前位置的check设为true，然后递归调用自己，返回后，进行回溯，将子节点从path移除，重新将check设为false.
最后是递归出口，当path的大小和nums的大小一样时，说明已经是一个完整的序列，可以将path添加到ret后，返回。
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
bool check[7];
void dfs(vector<int>& nums)
{
if(path.size() == nums.size())
{
ret.push_back(path);
return ;
}
for(int i = 0; i < nums.size(); i++)
{
if(check[i] == false)
{
path.push_back(nums[i]);
check[i] = true;
dfs(nums);
path.pop_back();
check[i] = false;
}
}
}
vector<vector<int>> permute(vector<int>& nums)
{
dfs(nums);
return ret;
}
} ;子集
78. 子集 - 力扣（LeetCode）
和上一道题类似，我们依旧是先画出决策树，再根据决策树找出重复的子问题，编写递归函数。在这里，我将画出两种决策树，并分别编写对应的代码。
首先，第一种决策树的思路是：我们在树的每一层进行判断是否选择某个数组元素，这样一来，当我们遍历完数组时，决策树的叶子节点就是符合条件的数组了。
在这里，我们同样使用全局变量来进行优化，最后需要返回的二维数组ret和暂时存放结果的数组path都可以定义为全局变量。接着，我们开始考虑dfs函数所需要做的事情，对于决策树的每个节点，dfs要做的事情无非是：存放数组元素的情况，此时需要把当前数组元素存到path，然后递归调用自己，进入决策树的下一层；不存放数组元素的情况，此时不需要把当前数组元素存到path，直接递归调用自己，进入决策树的下一层。于是我们的递归函数除了需要传入数组nums外，还需要传入当前遍历到的nums下标pos的位置。
最后，如果我们想要正确编写代码，还需要考虑一些细节问题：1.递归出口：很简单，当pos越界时，我们的决策树已经考虑完了所有的情况，这时候就能将path添加到ret中，然后返回。2.是否进行剪枝，显然我们的决策树是不需要剪枝的。3.如何进行回溯，在存放数组的情况下，我们需要把数组元素添加到path中，所以在这种情况dfs完后，我们需要把这个数组元素从path中删除，这种恢复现场的操作，就是回溯。
class Solution {
public:
vector<int> path;
vector<vector<int>> ret;
vector<vector<int>> subsets(vector<int>& nums)
{
dfs(nums, 0);
return ret;
}
void dfs(vector<int> &nums, int i)
{
if(i == nums.size()) --- 当i越界时，直接返回
{
ret.push_back(path);
return ;
}
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
dfs(nums, i + 1);
}
};第二种决策树，我们设计让决策树的每一层从指定的位置开始遍历数组，对每个数组元素的情况分别进行dfs，并且向dfs传入的指定位置就是数组元素的下标，这样一来就保证了我们能够不重不漏地找出所有子集。在这种情况下，我们在决策树的每个节点都将path添加到ret中。
class Solution {
public:
// 解法二：决策树每个节点都是返回值
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> subsets(vector<int>& nums)
{
dfs(nums, 0);
return ret;
}
void dfs(vector<int> &nums, int pos)
{
ret.push_back(path);
for(int i = pos; i < nums.size(); i++)
{
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
}
}
};括号生成
22. 括号生成 - 力扣（LeetCode）
本题的决策树非常的简单，我们只需要在每层判断选择左括号还是右括号即可，但是显然这棵决策树是有不少不符合条件的树枝的，所以需要进行剪枝。
为了对决策树进行剪枝，我们首先要先明确一下有效的括号组合是什么？ 1.左括号的数量等于右括号的数量。2.对从头开始的子串而言，左括号的数目大于等于右括号的数目。所以我们就根据这两点进行剪枝。
和前面的题目类似，我们使用全局变量来简化代码，首先是一个存储单次dfs结果的字符串path，还有存放结果的字符串数组ret，除此之外，为了根据左括号和右括号的数量进行剪枝，我们还需要用left和right分别表示左右括号的数量。
接下来，让我们思考一下dfs函数在某一个节点中具体需要完成什么任务。dfs需要对左括号和右括号的情况进行深度优先遍历，并且在左括号处理完成后，需要恢复现场，然后去处理右括号。
最后是递归出口，当我们的右括号等于n时，根据有效括号的性质，左括号必定也等于n，此时我们就找到了一个有效括号组合，将path存入ret后，返回即可。
class Solution {
public:
int left, right, n;
string path;
vector<string> ret;
vector<string> generateParenthesis(int _n)
{
n = _n;
dfs();
return ret;
}
void dfs()
{
if(right == n)
{
ret.push_back(path);
return ;
}
if(left < n)
{
path.push_back('('), left++;
dfs();
path.pop_back(), left--;
}
if(right < n && right < left)
{
path.push_back(')'), right++;
dfs();
path.pop_back(), right--;
}
}
};