算法学习记录：递归

        递归算法的关键在于回复现场，dfs（）函数返回值、结束条件、它的作用。

        

目录

1.综合练习

2. 二叉树的深搜

---

1.综合练习

         39. 组合总和 - 力扣（LeetCode）

         关键在画出的决策树当中，前面使用过的2、3，后面的3、2，就不需要再次使用了，下次是从 i 位置开始继续向下进行递归操作。同时需要注意当 sum 的值超过 aim 的时候就需要结束循环条件。（因为刚做过就不画出详细的图片了）

class Solution {
public:int aim = 0;vector<vector<int>> ret;vector<int> path;unordered_map<int, vector<int>> hash();vector<vector<int>> combinationSum(vector<int>& candidates, int target){aim = target;dfs(candidates, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int sum){if(aim == sum){ret.push_back(path);return;}//如果是加的特别多了，就要向前进行返回if(sum > aim || pos >= nums.size()){return;}for(int i = pos; i < nums.size(); i++){path.push_back(nums[i]);dfs(nums, i, sum += nums[i]);//递归到当前的位置继续进行选择，进行递归的是下一次的和，要不然返回来的时候sum -= nums[i];path.pop_back();}}
};

         494. 目标和 - 力扣（LeetCode）

       

        加 或者是 减有两种情况可以。注意最后的返回是 nums.size() == n 即可。

class Solution {
public:int cnt = 0,sum = 0,n = 0,_target = 0;int findTargetSumWays(vector<int>& nums, int target) {//使用 dfs，进行暴力传递 nums，以及pos位置n = nums.size();_target = target;dfs(nums, 0);//从 0 位置开始进行递归 return cnt;}void dfs(vector<int>& nums, int pos){if(nums.size() == pos){if(sum == _target) cnt++;return ;}//进行分别进行选与不选的操作sum += nums[pos];dfs(nums, pos + 1);sum -= nums[pos];sum -= nums[pos];dfs(nums, pos + 1);sum += nums[pos];}

2. 二叉树的深搜

 2331. 计算布尔二叉树的值 - 力扣（LeetCode） 

       计算布尔值，知道左子树的布尔值，右子树的布尔值，以及此时根结点的布尔值，如此一来，这就是一个后续遍历二叉树。定义 dfs(TreeNode* root),返回值就是布尔值。关键在于以当前的位置为视角去判断左右子树。(由于是二次刷题，此处只展示核心代码部分).   

if(root->left == NULL && root->right == NULL) return root->val == 0 ? false : true;bool left = evaluateTree(root->left);bool right = evaluateTree(root->right);if(root->val == 2) {return left | right;}else return left & right;

 206. 反转链表 - 力扣（LeetCode）

     

          这道题不是二叉树深搜的题目，是一道寻找子问题的题目,但是还是需要进行一次深度优先遍历dfs(ListNode* head),这个函数的操作就是将 head 以后的结点后进行翻转操作。

        子问题为：进行到当前的位置，如果是他的下一个位置不为 NULL，就需要将他下一个的下一个指向头位置.

if(head == NULL || head->next == NULL) return head;ListNode* Fhead = reverseList(head->next);head->next->next = head;head->next = NULL;return Fhead;

 129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

        

        需要注意的是，在这个函数里面 ret 的不可定义为全局的变量，因为我们控制的 dfs 的意义为在当前位置的时候计算一下左右子树的和。其实每回进行的时候 ret 都要初始化为 0；

int sumNumbers(TreeNode* root) {//通过递归进行实现，现在一个函数已经无法满足return dfs(root, 0);//dfs 返回的是当前点加上 左右结点的和，还有另外一个函数表示的是到当前位置的时候此时前面的和}int dfs(TreeNode* root, int pernum){int ret = 0;//dfs 表示从 0 开始向下进行遍历的求和pernum = pernum * 10 + root->val;if(root->left == NULL && root->right == NULL){return pernum;}//相当于遍历到了最后的一个位置，然后计算左右子树的和if(root->left) ret += dfs(root->left, pernum);if(root->right) ret += dfs(root->right, pernum);return ret;}

 814. 二叉树剪枝 - 力扣（LeetCode）

        一看到这种题，就应当想到以当前位置结点，判断左子树，右子树的情况，如果是当前位置空直接返回，当前位置的左为空，右为空，同时 root->val == 0。我们就将当前位置变成 NULL；

TreeNode* pruneTree(TreeNode* root) {//通过分析判断得到，这个函数跟我想要的一样if(root == nullptr) return nullptr;//1.分别处理左右子树root->left = pruneTree(root->left);root->right = pruneTree(root->right);//处理完之后去处理一下根if(root->left == nullptr && root->right == nullptr && root->val == 0){root = nullptr;}return root;}

98. 验证二叉搜索树 - 力扣（LeetCode）

        这道题需要使用 搜索二叉树的一个性质为：中序遍历完全符合升序的特点，如果是不符合就使用剪枝进行返回一个 false。dfs（）表示以当前的位置为结点时候为二叉搜索树，返回值为 ture 或者是 false,递归出去的条件为：左右子树都为空的情况。

long prev = LONG_MIN;
if(root->left == NULL && root->right == NULL) return true;//一个结点肯定是二叉搜索树//需要判断左子树的 boolbool left = isValidBST(root->left);if(left == false) return false;//判断 根时候符合bool tmp = false;if(root->val > perv) tmp = true;perv = root->val;//进行剪枝if(tmp == false) return false;//判断右子树bool right = isValidBST(root->right);if(right == false) return false;if(right && left && tmp) return true;return false;//照顾编译器，防止最后出错

 230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

 dfs(TreeNode* root)就是进行遍历，当前结点为 NULL 的时候进行返回。需要定义全局变量 cnt 表示进行到了第几个，ret 表示最后的结果。每次判断根部的时候就cnt --；

class Solution {
public://定义两个全局变量，一个表示还需要进行的次数，直到小于 0 为止，另外一个表示最后的结果// int cnt;// int ret;void dfs(TreeNode* root){if(root == NULL || cnt == 0 ) return;dfs(root->left);cnt--;if(cnt == 0){ret = root->val;return;} dfs(root->right);}int kthSmallest(TreeNode* root, int k) {// cnt = k;// dfs(root);//通过深度优先遍历来修改ret的值// return ret;cnt = k;dfs(root);return ret;}int cnt = 0;int ret = 0;

257. 二叉树的所有路径 - 力扣（LeetCode）

        dfs(root, path)，除了定义一个 root，还需要定义一个path，表示通过的路径。如果不在这里定义就需要将遍历一遍就进行复原。定义一个 path 会方便很多。

/*** 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://定义两个全局变量//string path;vector<string> ret;vector<string> binaryTreePaths(TreeNode* root) {string path;dfs(root, path);return ret;}void dfs(TreeNode* root, string path){path += to_string(root->val);if(root->left == NULL && root->right == NULL){ret.push_back(path);return;}path.push_back('-');path.push_back('>');if(root->left) {dfs(root->left, path);  }if(root->right){dfs(root->right, path);}}
};

 46. 全排列 - 力扣（LeetCode）

        经典中的经典。

class Solution {
public:vector<vector<int>> ret;//表示最后结果vector<int> path;//走的路径bool used[8];//表示当前的数是否被使用了vector<vector<int>> permute(vector<int>& nums) {dfs(nums);//从 0 位置开始进行遍历return ret;}void dfs(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(used[i] == false){path.push_back(nums[i]);used[i] = true;dfs(nums);path.pop_back();used[i] = false;}}}
};