主要参考：
文章目录- 递归思想
- 函数模板
- leetcode部分题目
- 965. 单值二叉树
- 104. 二叉树的最大深度
- 543. 二叉树的直径
- 110. 平衡二叉树
- 101. 对称二叉树
- 226. 翻转二叉树
- 98. 验证二叉搜索树
- 105. 从前序与中序遍历序列构造二叉树
- 236. 二叉树的最近公共祖先
- 1022. 从根到叶的二进制数之和
递归的思路：
重复利用函数本身能实现的功能，按照顺序进行不断地自调用
核心: 建立递归函数
函数主要包含:
1.边界判断
2.实现需要完成的功能
3.对下一跳/项继续进行函数自身的调用
什么时候递归需要返回值：
参考：二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？
如果需要搜索整颗二叉树（遍历到所有节点），那么递归函数就不要返回值，
如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。
函数模板1.这个问题的子问题是什么。
2.当前层要干什么事情。
3.递归出口。想清楚这几点就好啦。
很多刚接触递归的同学习惯往深处想，就想想清楚下一层，下下层到底咋回事，千万别！这样永远也想不清楚的，你只要把当前层的事情干好，边界条件找好，深层自然而然就是对的。千万别想那么深。
递归函数function(当前节点){
终止条件判断(遍历到尽头直接 return)
剪枝条件判断(return)
访问该节点（根据题意修改节点状态）
对左节点调用function
对右节点调用function
}
主函数( ){
对根节点调用函数function
返回结果
}
leetcode部分题目
leetcode中对二叉树的定义
965. 单值二叉树
965. 单值二叉树
思路：
因为需要遍历到二叉树中的每一个节点（判断其是否相同），因此递归不需要返回值。
定义一个全局变量ans，便于剪枝。
class Solution {
public:
bool ans=true;
void DFS(TreeNode* root,int val){
if(root==NULL){//边界
return;
}
if(ans==false){//剪枝
return;
}
//访问当前节点
if(root->val!=val){
ans=false;
return;
}
//扩展方式 只有两种 故 直接写
DFS(root->left,val);
DFS(root->right,val);
}
bool isUnivalTree(TreeNode* root) {
int val=root->val;
DFS(root,val);
return ans;
}
};
104. 二叉树的最大深度
104. 二叉树的最大深度
思路：
需要遍历到二叉树中的每一个节点，因此不需要返回值
可以维护一个全局变量，记录其当前的最大的深度
参考：代码随想录
DFS写法：
class Solution {
public:
int max_depth=0;
void DFS(TreeNode* root,int depth){
if(root==NULL){
return;
}
depth+=1;//修改状态
max_depth=fmax(max_depth,depth);//更新最大深度
DFS(root->left,depth);
DFS(root->right,depth);
depth-=1;//恢复状态
}
int maxDepth(TreeNode* root) {
DFS(root,0);
return max_depth;
}
};
更简洁递归写法：
子问题：
对现在访问的节点（这一层）进行深度累加
求树的最大深度，需要从每一级得到的信息自然是当前这一级对应的树的最大深度，因此返回值应该是当前树的最大深度
当前层要干什么：
在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度了，然后再返回这个深度即可
递归出口：
树为空的时候，此时树的深度为0，递归就结束了。
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL){
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
//返回的是左右子树的最大深度+1
return max(leftDepth, rightDepth) + 1;
}
};
543. 二叉树的直径
543. 二叉树的直径
思路：
需要遍历到二叉树中的每一个节点（最大直径不一定经过根节点）
可以维护一个全局变量，记录其当前的最大的直径
但是！最大直径需要两个节点的值加起来 这就要求递归函数应该返回一个值，便于我们想加。
class Solution {
public:
int ans;
//递归求深度
int depth(TreeNode* root){
// 访问到空节点，返回0;p高度增加0
if (root == NULL) {
return 0;
}
int L = depth(root->left); // 左儿子为根的子树的深度
int R = depth(root->right); // 右儿子为根的子树的深度
ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
return max(L, R) + 1; // 返回该节点为根的子树的深度
}
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
depth(root);
return ans-1;
}
};
110. 平衡二叉树
110. 平衡二叉树
思路：
平衡二叉树要求每个节点都要满足平衡的条件，但是判断平衡需要他左右子树返回一个高度值进行比较，这就要求递归函数应该返回一个值，便于我们判断。
可以维护一个全局变量记录是否平衡，便于剪枝
这题中没有使用全局变量，而是直接 return -1表示其不为平衡二叉树（剪枝）
梳理一下：
子问题：
对现在访问的节点（这一层）进行平很判断
当前层要干什么：
平衡二叉树要求每个节点都要满足平衡的条件，判断平衡需要他左右子树返回一个高度值进行比较，应为树的高度不可能为负数，因此设置-1作为不平衡的判断。
（1）如果root为空，说明走到尽头，直接返回0（高度为0）
（2）判断当前节点（这一层）是不是平衡的，
不平衡 L==-1 || R==-1 || abs(L-R)>1 ，返回-1
平衡 返回 max(L,R)+1（当前节点的最大高度/深度）
int L=height(root->left); int R=height(root->right); 为打包好的（下一层的）高度，
递归出口：
树为空的时候，空树是平衡的，递归就结束了。
自底向上的递归
则对于每个节点，函数 height 只会被调用一次
(及时止损 )
class Solution {
public:
//返回值为int 是因为他需要返回一个高度进行比较
//因为函数内部的值只能通过指针或者返回得到
//其实和求二叉树的深度的题目非常的相似
int height(TreeNode* root){
if(root==NULL){//边界
return 0;
}
int L=height(root->left);
int R=height(root->right);
if(L==-1 || R==-1 || abs(L-R)>1 ){
//return -1就代表失败
return -1;
}
else{
//要加上当前节点的高度
return fmax(L,R)+1;
}
}
bool isBalanced(TreeNode* root) {
return height(root)>=0;
}
};
自顶向下的递归
因此对于同一个节点，函数height 会被重复调用，导致时间复杂度较高
(不管三七二十一先把所有的高度算一遍)
class Solution {
public:
//height函数单纯的只计算高度
int height(TreeNode* root) {
if(root == NULL){
return 0;
} else {
return max(height(root->left), height(root->right)) + 1;
}
}
bool isBalanced(TreeNode* root) {
if(root == NULL){
return true;
}
else{
return abs(height(root->left) - height(root->right)) <= 1
&& isBalanced(root->left)
&& isBalanced(root->right);
}
}
};
101. 对称二叉树
101. 对称二叉树
思路：
在某些情况下不需要遍历完所有的节点，可以剪枝，故可以返回bool形式的
class Solution {
public:
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) //两个都不存在
return true;
if (!p || !q) //两个中存在一个
return false;
//两个都存在
if(p->val != q->val)
return false;
//扩展情况 左右节点
bool ans=true;
ans=check(p->left, q->right)
&& check(p->right, q->left);
return ans;
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
226. 翻转二叉树
226. 翻转二叉树
思路：
每个节点都要遍历到，从根节点开始，对每一个访问到的节点交换其左右子树
class Solution {
public:
void change(TreeNode *root){
if(root==NULL) //边界，访问到尽头
return;
//左右节点都在 进行交换(相当于是状态修改)
auto node=root->left;
root->left=root->right;
root->right=node;
//拓展情况
change(root->left);
change(root->right);
return;
}
TreeNode* invertTree(TreeNode* root) {
change(root);
return root;
}
};
98. 验证二叉搜索树
98. 验证二叉搜索树
思路：
在某些情况下不需要遍历完所有的节点，可以剪枝，故可以返回bool形式的
从根节点开始，对每一个访问到的节点 进行验证
注意，这里不单单是验证左右两个节点，而是要验证左右两个子树
故可以在递归中维护 lower upper 便于验证。
class Solution {
public:
bool helper(TreeNode* root, long long lower, long long upper) {
if(root==NULL){
return true;
}
//验证 左<根<右
if(root->val<=lower || root->val>=upper){
return false;
}
//验证左子树 LONG_MAX=root->val
//验证右子树 LONG_MIN=root->val
bool ans;
ans= helper(root->left,lower,root->val)
&& helper(root->right,root->val,upper);
return ans;
}
bool isValidBST(TreeNode* root) {
return helper(root, LONG_MIN, LONG_MAX);
}
};
105. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
思路：
前序遍历：根左右
中序遍历：左根右
构造哈希映射（中序遍历）——》快速找到当前根节点 在 中序遍历序列中的位置
class Solution {
public:
unordered_map index;
TreeNode* myBuildTree(const vector& preorder, const vector& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){
//递归边界
if(preorder_left>preorder_right || inorder_left>inorder_right){
return nullptr;
}
//前序遍历的第一个节点为当前根节点
int curroot=preorder[preorder_left];
//定位到其在inorder中的位置
int currootindex=index[curroot];
//左子树长度
int subleftTree=currootindex-inorder_left;
//因为返回的是一个节点
//所以应该新建一个节点
TreeNode *root=new TreeNode(curroot);
root->left=myBuildTree(preorder,inorder,preorder_left+1,preorder_left+subleftTree,inorder_left,currootindex-1);
root->right=myBuildTree(preorder,inorder,preorder_left+subleftTree+1,preorder_right,currootindex+1,inorder_right);
return root;
}
TreeNode* buildTree(vector& preorder, vector& inorder) {
int n = preorder.size();
// 构造哈希映射
// 快速找到当前根节点 在 中序遍历序列中的位置
for (int i=0;i
index[inorder[i]] = i;
}
// for(auto x:index){
// cout<
236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先
思路：（有参考别人的题解）
公共：两个节点的祖先一定在 从根节点到这两个节点的路径上
最近：即同时出现在这两条路径上离根节点最远的节点，或者离这两个节点最近的地方
求法：
1、求从根节点到 p路径、q路径 （DFS求）
2、寻找两路径上最后一个相同的节点 （遍历求）
class Solution {
public:
void DFS(TreeNode *root,TreeNode *search,vector &path,vector &final_path,int finish){
if(root==NULL || finish==1)//边界
return;
path.push_back(root);//修改状态
if(root==search){
finish=1;
final_path=path;
}
DFS(root->left,search,path,final_path,finish);
DFS(root->right,search,path,final_path,finish);
path.pop_back();//恢复状态
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector path;
vector p_path;
vector q_path;
int finish=0;
DFS(root,p,path,p_path,finish);
path.clear();
DFS(root,q,path,q_path,finish);
int len=fmin(q_path.size(),p_path.size());
TreeNode *res;
for(int i=0;i
if(q_path[i]==p_path[i]){
res=q_path[i];
}
}
return res;
}
};
1022. 从根到叶的二进制数之和
1022. 从根到叶的二进制数之和
思路：
- 保存从根节点到叶子节点的每一条路径 （DFS）
- 将 每一条路径 2进制=》10进制 相加（count）
注意：
因为会出现 [1,1] 这种测试用例，故题目不保证为完全二叉树
因此在边界处理时，不能以 常见的 root==NULL ，因为这样就会重复存储路径。（左右节点都为空）
应该以 root->left==NULL && root->right==NULL 确定。
class Solution {
public:
vector> path;
vector cur_path;
void DFS(TreeNode* root){
if(root->left==NULL && root->right==NULL){//边界
cur_path.push_back(root->val);//修改状态 因为当前节点还未访问
path.push_back(cur_path);
cur_path.pop_back();//恢复状态
return;
}
//访问当前节点
cur_path.push_back(root->val);//修改状态
//扩展状态
if(root->left)
DFS(root->left);
if(root->right)
DFS(root->right);
cur_path.pop_back();//恢复状态
}
int count(vector> &path){
int ans=0;
for(auto & a_path:path){
int n=0;
for(int i=0;i
if(a_path[i]==1)
n+=pow(2,a_path.size()-1-i);
}
ans+=n;
}
return ans;
}
int sumRootToLeaf(TreeNode* root) {
DFS(root);
return count(path);
}
};
