本博客是leetcode上图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台的刷题记录，可能存在错误，仅供参考。
主要记录刷题过程的思路，错误，代码以及总结，更详细的解答可以直接看上面这本书。
如发现错误，欢迎在评论区指正，我会及时修改。
同时也希望大家能在评论区多和我讨论，或者私信我，讨论可以让我们学习效率更高。
现在的版本不是最终版本，我会在学习过程中不断地更新。
这是我的gitee账号
shumoke/Leetcode-brushing-record - 码云 - 开源中国 (gitee.com)
里面有更加齐全的代码
题目
方法1：回溯
思路：
遍历每个根节点，然后交换其左右子数，然后再访问其左右子数继续交换。这是从上到下进行交换。
代码：
public TreeNode mirrorTree(TreeNode root) {
reverse(root);
return root;
}
void reverse(TreeNode root){
if(root==null) return ;
TreeNode tmp;
tmp=root.left;
root.left=root.right;
root.right=tmp;
//遍历根节点的左右节点
reverse(root.left);
reverse(root.right);
}
注意：
要注意函数的返回值，此函数的返回值是TreeNode类型，递归函数中只有在上层的解需要下层的解时，递归终止条件中才会返回值，不然只需要返回执行权就可。
如果下面的代码被放在if(root.left!=null&&root.right!=null)中，会导致叶子节点和非叶子节点不进行交换，对于一些特例，无法形成镜像。
TreeNode tmp;
tmp=root.left;
root.left=root.right;
root.right=tmp;
方法2：递归
时间复杂度：O(n)
空间复杂度：O(n)
//递归法
public TreeNode mirrorTree(TreeNode root) {
//递归终止
if(root==null) return null;
TreeNode node=root.left;
root.left=mirrorTree(root.right);
root.right=mirrorTree(node);
return root;
}
思路
对称二叉树定义： 对于树中 任意两个对称节点 L 和 R ，一定有：
L.val = R.val ：即此两对称节点值相等。
L.left.val = R.right.val ：即 LL 的 左子节点 和 RR 的 右子节点 对称；
L.right.val = R.left.val ：即 LL 的 右子节点 和 RR 的 左子节点 对称。
根据以上规律，考虑从顶至底递归，判断每对左右节点是否对称，从而判断树是否为对称二叉树。
代码
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iIMbL6f8-1666100552960)(算法刷题笔记.assets/image-20220923214911263.png)]
总结
将判断一个树是否是对称二叉树，分解成是否每一对对称的左右节点的对称情况。
疑问
什么时候用，什么时候用从底到顶的递归？
题目
思路
深度优先搜索：遍历矩阵中每个元素，在当前元素通过DFS递归，先往一个方向一直搜索，如果遇到不匹配选项，就返回到该元素，然后换一个方向去搜索。
剪枝：如果搜索一个方向，发现该方向有不匹配项，则立即返回，称为可行性剪枝。
DFS解析：
递归参数：
返回值：
1.返回res,代表是否搜索到了目标字符串
终止条件：
递推：
board[i][j] 修改为 空字符 '' ，代表此元素已访问过，防止之后搜索时重复访问。或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。board[i][j] 元素还原至初始值，即 word[k] ，这个得在递归结束后，才会一个个还原。时间复杂度：矩阵中所有元素都可以作为起点，共有NM个起点，所以时间复杂度为O(NM),对于每个起点，长度为K的字符串，搜索方案数为3的K次方（这个对应了回溯中，每一步面对的不同选项数），所有总的时间复杂度为***O*(3*K*M*N*)
空间复杂度：搜索过程中的递归深度不超过 K，因此系统因函数调用累计使用的栈空间占用 O(K) （因为函数返回后，系统调用的栈空间会释放）。最坏情况下 字符串K 的长度为=MN ，递归深度为 MN ，此时系统栈使用 **O(MN)**的额外空间。
代码
package com.回溯;
class Solution4 {
public boolean exist(char[][] board, String word) {
//将字符串转变为字符数组
char[] words = word.toCharArray();
// 遍历字符串
for(int i=0;i<board.length;i++){
for (int j = 0; j < board[0].length; j++) {
if(dfs(board,words,i,j,0)){
return true;
}
}
}
return false;
}
boolean dfs(char[][] board,char[] words,int i,int j,int k){
//终止条件
if(i<0||i>=board.length||j<0||j>board[0].length||board[i][j]!=words[k]) return false;
if(k==words.length-1) return true;
//递推
board[i][j]='\0';//将当前元素设置为空字符串（Python: '' , Java/C++: '\0'），防止重复访问
//递归当前元素的四个方向，下上右左，匹配下一个元素
boolean res=dfs(board,words,i+1,j,k+1)||dfs(board,words,i-1,j,k+1)||
dfs(board,words,i,j+1,k+1)||dfs(board,words,i,j-1,k+1);//有一个ture则整体为true
//将矩阵元素还原
board[i][j]=words[k];//因为上面有判断board[i][j]!=words[k]，它不成立，则board[i][j]=words[k]，所有这需要这样，就可以将矩阵还原。
return res;
}
}
public class 剑指Offer12矩阵中的路径 {
public static void main(String[] args) {
}
}
总结
在终止条件中就会进行判断，或者保存结果
空字符（Python: ‘’ , Java/C++: ‘\0’ ）
递归的时间复杂度为O(2^N)指数阶
总结
代码
package com.回溯;
import java.util.LinkedList;
import java.util.List;
class Solution6 {
LinkedList<List<Integer>> res=new LinkedList<>();// 存放所有满足条件的路径
LinkedList<Integer> subset=new LinkedList<>();//存放正在寻找的路径
public List<List<Integer>> pathSum(TreeNode root, int target) {
dfs(root,target,subset,res);
return res;
}
void dfs(TreeNode root,int target,LinkedList<Integer> subset,LinkedList<List<Integer>> res){
//终止条件
if(root==null){
return;
}
subset.add(root.val);
// int sum=0;
// for (int e:subset) {
// sum+=e;
// }
//改进上面发for循环
target-=root.val;
if(target==0&&root.left==null&&root.right==null){
res.add(new LinkedList<>(subset));//找到一条满足条件的路径，将其添加到结果列表中,一定要new一个，不然后对subset进行操作，结果里面的值也会变。
}
//递推开始
dfs(root.left,target,subset,res);
dfs(root.right,target,subset,res);
subset.removeLast();
}
}
public class 剑指Offer34二叉树中和为某一值的路径 {
public static void main(String[] args) {
}
}
错误
bug
1.java.lang.IndexOutOfBoundsException: Index: 7, Size: 0
at line 559, java.base/java.util.LinkedList.checkElementIndex
at line 529, java.base/java.util.LinkedList.remove
at line 46, Solution.dfs
at line 44, Solution.dfs
at line 44, Solution.dfs
at line 44, Solution.dfs
at line 21, Solution.pathSum
at line 54, DriverSolution.helper
at line 87, Driver.main
原因：应该分remove函数有关，在递归到下一层时，subset.remove删除了一些元素，但是在上层中这个元素还在，出现了索引异常，所以在递归中使用全局变量时一定要注意。可以用removeLast()来代替remove(object o)，但要注意removeLast()是LinkedList特有的办法，remove(object o)是所有Collection集合都有的办法。
总结
题目
思路
利用二叉树的中序遍历的元素顺序是递归的这一性质进行解题
中序遍历访问的第一个节点就是双向链表的第一个节点
时间复杂度:O(N)
空间复杂度：O(N)
代码
package com.回溯;
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
}
class Solution7 {
//定义前结点和当前结点
Node pre,head;
public Node treeToDoublyList(Node root) {
if(root==null) return null;
//进行中序遍历
dfs(root);
//将链表头尾相连，形成循环链表
head.left=pre;
pre.right=head;
return head;
}
void dfs(Node cur){
if(cur==null) return;
dfs(cur.left);
//没有前驱结点则为第一个结点
if(pre!=null) pre.right=cur;
else head=cur;
cur.left=pre;
pre=cur;
dfs(cur.right);
}
}
public class 剑指Offer36二叉搜索树与双向链表 {
public static void main(String[] args) {
}
}
总结
不用固定思维在先序遍历上，可以利用中序遍历的元素递增性质进行解题
二叉树的深度遍历时间复杂度为O(N),在回溯中有些递归的复杂度是k的N次方。
疑问
回溯和搜索的区别是什么？
中序遍历属于回溯吗？
1.题目
2.思路
中序深度遍历，中序遍历二叉搜索树得到的序列是递增的
3.代码
package com.回溯;
import java.util.ArrayList;
class Solution8 {
//法一:将root.val添加到ArrayList中
ArrayList arr=new ArrayList();
public int kthLargest(TreeNode root, int k) {
dfs(root);
int len=arr.size();
int res= (int) arr.get(len-k);
return res;
}
void dfs(TreeNode root){
if(root==null) return;
dfs(root.left);
arr.add(root.val);
dfs(root.right);
}
//法二：求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。
int res,k;
public int kthLargest2(TreeNode root, int k) {
this.k=k;
dfs2(root,this.k);
return res;
}
void dfs2(TreeNode root,int k){
if(root==null || k==0) return;
dfs(root.right);
if(--k==0) res=root.val;
dfs(root.left);
}
}
public class 剑指Offer54二叉搜索树的第k大节点 {
public static void main(String[] args) {
}
}
4.总结
求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”,中序遍历倒序就是先遍历右子数（这个不容易想到）
刚开始审题错误，以为中序遍历后不是自然数，所以需要注意审题
要有转化的思想，当直接解决不好解决时，看看能不能换个角度去解决
–k和k–的区别
1.题目
2.方法
法一：回溯法
思路：先dfs遍历所有的路径，然后把每一条路径都存到LinkedList中，然后比较路径的最大值，即为结果。
时间复杂度：O(n)
空间复杂度：O(n*2) #疑问
代码：
package com.回溯;
import java.util.LinkedList;
import java.util.List;
class Solution9 {
LinkedList<List<Integer>> res=new LinkedList<>();
LinkedList<Integer> path=new LinkedList<>();
public int maxDepth(TreeNode root) {
if(root==null) return 0;
dfs(root);
int maxdepth=0;
for (List p:res) {
if(p.size()>maxdepth) maxdepth=p.size();
}
return maxdepth;
}
void dfs(TreeNode root){
//终止条件
if(root==null) {
res.add(new LinkedList<>(path));//将此条路径存入结果中,注意：要这样添加new LinkedList<>(path)，然后path还原后res中的值也会变
return;
}
//递推
path.add(root.val);
dfs(root.left);
dfs(root.right);
path.removeLast();//回溯前将路径还原，用于存放新的路径
}
}
public class 剑指Offer55I二叉树的深度 {
public static void main(String[] args) {
}
}
5.总结：这种方法的效率很低，时间和空间都低
法二：后序遍历
思路：采用后序遍历（至下往上递归），该树的深度等于其左子树深度和右子数深度的最大值+1
代码
//法二:后序遍历（至下往顶递归），该树的深度等于其左子树深度和右子数深度的最大值+1
public int maxDepth2(TreeNode root) {
if(root==null) return 0;
// int leftDepth=maxDepth(root.left);
// int rightDepth=maxDepth(root.right);
// return Math.max(leftDepth,rightDepth)+1;
//上面3句合并后为
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
时间复杂度：O(n)
空间复杂度：O(n)，树退化成链表时
提交结果
总结：
法三：层序遍历
思路：层次遍历，累计层数
代码：
//法三：层次遍历，累计层数
public int maxDepth3(TreeNode root) {
if(root==null) return 0;
//定义一个队列
// List<TreeNode> queue = new LinkedList<TreeNode>(){{add(root);}},tmp;//这句改写成下面两句
List<TreeNode> queue = new LinkedList<TreeNode>(),tmp;
queue.add(root);
int res=0;
while(!queue.isEmpty()){
tmp=new LinkedList<TreeNode>();
for (TreeNode e:queue
) {
if(e.left!=null) tmp.add(e.left);
if(e.right!=null) tmp.add(e.right);
}
queue=tmp;
res++;
}
return res;
}
时间复杂度：O(n)
空间复杂度：O(n)，最差情况下（当树平衡时），队列 queue 同时存储 N*/2 个节点
提交结果：
总结：
1.题目
2.方法
1）法一：从底向顶递归
2）法二：后序遍历+剪枝
思路：
代码：
//法二：后序+剪枝判断（即在后序遍历中直接判断）
public boolean isBalanced(TreeNode root) {
return recur(root)!=-1;
}
int recur(TreeNode root){
//终止条件
if(root==null) return 0;
//递推
int leftDepth=recur(root.left);
if(leftDepth==-1) return -1;//如果左子数已经是不平衡的，则直接返回不平衡
int rightDepth=recur(root.right);
if(rightDepth==-1) return -1;//如果右子数已经是不平衡的，则直接返回不平衡
//返回值
//如果左子数-右子数的绝对值小于等于1，则返回该节点的深度，否则返回-1，代表不平衡。
return Math.abs(leftDepth-rightDepth)<=1?Math.max(leftDepth,rightDepth)+1:-1;
}
复杂度分析：
时间复杂度：O(n)
空间复杂度：O(n)，二叉树退化成链表时
总结
1.递归的终止条件分类
2.用递归做判断时，要考虑多种可能情况，可能会用到|| 和&&逻辑运算法