【算法专题】搜索算法

 二叉树剪枝

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;}
} ;