递归三要素
树和链表都是天然的递归结构
1. 明确函数的作用
由我们自己定义
2. 寻找递归终止条件
递归就是函数自己调用自己，当参数为什么时，我们能够直接知道函数的结果，这时递归终止，将函数值进行返回
3. 找出函数的等价关系式（等价操作步骤）
我们不断缩小参数的范围，缩小之后要通过辅助的变量或操作使原函数的结果不变
侧重于函数的功能，忽略实现步骤
- 辅助的变量（缩小参数范围+变量）：适用于数字计算之类的题目
f(n)=n*f(n-1) - 操作（缩小参数范围+操作）：适用于有节点的数据结构（链表，树）
reverseList(head)等价于reverseList(head.next)+改变一下1、2两个节点的指向
3.1 经验之谈
当我们在具有节点的数据结构中使用递归时，递归返回值有两类
- 我们要返回找到的节点
直接return 递归函数(缩小范围的参数);因为我们函数的目的是为了找到某个节点，所以getNode(node.left, key)与getNode(node, key)是等价的，最终结果都是同一个节点
//返回以node为根的二分搜索树中，键为key的节点
//返回的是当前节点
privateNodegetNode(Nodenode,Kkey){
//如果根为空，返回null
if (node==null)
returnnull;
//key<根节点的key,去左子树中寻找，缩小参数范围
if (key.compareTo(node.key)<0)
returngetNode(node.left, key);
//key>根节点的key
if (node.key.compareTo(key)>0)
returngetNode(node.right, key);
//key==node.kay
elsereturnnode;
}
- 我们要返回增删之后新的二分搜索树的根
remove(node.left)显然不与remove(node)等价，因此我们要进行一些操作，使其等价node.left=remove(node.left);return node;
//移除以node为根的二分搜索树中最小的节点
//返回移除后新的二分搜索树的根
privateNoderemoveMin(Nodenode){
//递归终止条件
//当前节点的左子树为空，那么就为最小节点。
//可能其还有右子树，我们提取出来他的右子树，其右节点理所当然成为新的二分搜索树的根
if (node.left==null){
//保存被删节点的右子树
NoderightNode=node.right;
//将被删除的节点从当前二叉树中脱离关系
node.right=null;
size--;
returnrightNode;
}
//removeMin(node)等价于removeList(node.left)+改变node.left指向新的右子树的根
node.left=removeMin(node.left);
returnnode;
}
递归的优化
1. 记忆化搜索（避免重复计算）
2. 动态规划（自底向上）
递归、回溯、dfs（深度优先搜索）、动态规划
- 递归：自我调用（作为编程的一种实现方式），dfs、回溯、动态规划都可以用递归来实现，也可以用非递归实现：
- 回溯：一种算法思想，把问题分步解决，在每一步都试验多有的可能，当发现已经找到一种方式或者当前这种方式不可能是结果，就退回上一步尝试其他可能（回溯可以用于所有用穷举法可以解决的问题）
- dfs：回溯用于树的时候就是dfs。几乎所有可以用回溯解决的问题都可以表示为树，如果显式的使用了树，那么就叫dfs（两者都可以剪枝算法）
- 动态规划：拥有最优子结构
回溯
解决一个回溯问题，实际就是一个决策树（在每个节点上都在做决策）的遍历过程。只需要思考三个问题：
- 路径：已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件：到达决策树底层，无法再做选择的条件（路径==选择列表长度）
46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
#include<iostream>;
#include<vector>;
usingnamespacestd;
classSolution {
private:
vector<vector<int>>res;
vector<int>e;
voidrecursion(vector<int>&e, vector<int>&nums) {
if (e.size() ==nums.size()) {
res.push_back(e);
return;
}
for (inti=0; i<nums.size(); i++) {
// if (count(e.begin(), e.end(), nums[i])!=0)
// continue;
if(find(e.begin(),e.end(),nums[i])!=e.end())
continue;
e.push_back(nums[i]);
recursion(e, nums);
e.pop_back();
}
return;
}
public:
vector<vector<int>>permute(vector<int>&nums) {
res.clear();
e.clear();
recursion(e, nums);
returnres;
}
};
17. 电话号码的字母组合
#include<iostream>;
#include<vector>;
usingnamespacestd;
classSolution {
private:
vector<string>res;
//路径
strings;
//字母与坐标的映射
conststringletterMap[10] = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
voidfindCombinations(stringdigits,intindex) {
//路径长度==数字字符串长度
if (s.size() ==digits.size()) {
res.push_back(s);
return;
}
charc=digits[index];//数字
stringletters=letterMap[c-'0'];//数字对应的字符串选择列表（选择列表）
for (intj=0; j<letters.size(); j++) {
s.push_back(letters[j]);
findCombinations(digits, index+1);
s.pop_back();
}
return ;
}
public:
vector<string>letterCombinations(stringdigits) {
s="";
res.clear();
if (digits=="")
returnres;
findCombinations(digits, 0);
returnres;
}
};
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
classSolution {
public:
//返回以root为根的二叉树的最大深度
intmaxDepth(TreeNode*root) {
//终止条件
if(root==NULL)
return0;
//方法1
// //左子树的最大深度
// int depth1 =maxDepth(root->left);
// //右子树的最大深度
// int depth2 =maxDepth(root->right);
// return depth1 > depth2 ? depth1+1 : depth2+1;
//方法2
//return maxDepth(root->left)<maxDepth(root->right)?maxDepth(root->right)+1:maxDepth(root->left)+1;
//方法3
returnmax(maxDepth(root->left),maxDepth(root->right))+1;
}
};
这里方法2会运行超时，我也不知道为什么
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
如果左子树为零，那么直接返回右子树即可！
classSolution {
public:
intminDepth(TreeNode*root) {
if(root==NULL)
return0;
intdepth1=minDepth(root->left);
intdepth2=minDepth(root->right);
if(depth1==0)
returndepth2+1;
elseif(depth2==0)
returndepth1+1;
else
returnmin(depth1,depth2)+1;
}
};
226. 翻转二叉树
翻转一棵二叉树。
以根节点为轴，翻转二叉树
classSolution {
public:
TreeNode*invertTree(TreeNode*root) {
if(root==NULL)
returnNULL;
//翻转左子树
invertTree(root->left);
//翻转右子树
invertTree(root->right);
//根节点进行交换
swap(root->left,root->right);
returnroot;
}
};
100. 相同的树
给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
classSolution {
public:
boolisSameTree(TreeNode*p, TreeNode*q) {
//先判断是否为空，再判断值，避免空指针异常
if(p==NULL&&q==NULL) returntrue;
if(p==NULL||q==NULL) returnfalse;
if(p->val!=q->val) returnfalse;
returnisSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
};
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==NULL)
return false;
//左子树和右子树都为空才为叶子节点
if(root->left==NULL&&root->right==NULL)
return root->val==targetSum;
if(hasPathSum(root->left,targetSum-root->val))
return true;
if(hasPathSum(root->right,targetSum-root->val))
return true;
return false;
}
};
收获
- 先判断节点是否为空，避免空指针异常
257. 二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
/**
* 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<string> binaryTreePaths(TreeNode* root) {
vector<string> str;
if(root==NULL)//传入节点为空，什么都不做
return str;
if(root->left==NULL&&root->right==NULL){
str.push_back(to_string(root->val));
return str;
}
vector<string> leftStr=binaryTreePaths(root->left);
for(int i=0;i<leftStr.size();i++)
str.push_back(to_string(root->val)+"->"+leftStr[i]);
vector<string> rightStr=binaryTreePaths(root->right);
for(int i=0;i<rightStr.size();i++)
str.push_back(to_string(root->val)+"->"+rightStr[i]);
return str;
}
};
收获
to_string：将int转换为string
