2024.01.21_学习日记
天气：雨夹雪
学习地点：家
学习时长：7h
学习内容
- 排序算法稳定性
- 反转单链表、双链表
反转单链表：注意要用一个tmp防止cur.next丢失，最后返回的是pre不是cur。
反转双链表：跟反转单链表一样，用一个tmp防止cur.next走丢，然后cru.next=pre,cur.last=tmp。 - 判断链表有没有环
快慢指针，相遇以后快指针回到head，然后快指针变成慢指针走一步，最后相遇就是入环节点。 - 判断两个链表相交节点
首先算出两个节点长度，然后长度相减得到一个值，最后让长链表先走这么多步，然后再一起走，走到交点就返回即可。还有一种情况是两个有环链表相遇，入环节点不一样，这个时候cur到第一个节点开始走，如果cur回到cur遇到了第二个节点，那就是这种情况，否则返回0。 - 二叉树遍历
递归遍历（先中后）：如果head空，返回空，然后print，再递归左，再递归右。
迭代遍历（先）：准备一个栈，先把头放进去，然后弹出来，打印，如果有右孩子和左孩子，先把右孩子压入栈，再左孩子压入栈，最后重复。
后序遍历（迭代）：准备两个栈，一个准备栈，一个收集栈。先把head放进准备栈，再弹出到收集栈，然后弹入左和右节点，再循环，最后打印收集栈即可。因为是按照头右左的方式弹出到收集栈，最后打印就是左右头。
中序遍历：如果头节点不为空，那就把头节点整个左边界压入栈，当左节点为空的时候，弹出节点，打印，然后head=右节点，再重复循环。
BFS宽度优先遍历：用队列。压入头节点，然后弹出打印，压入左右节点，继续周而复始。
求二叉树最大宽度：用队列。有几个变量，一个curlevel，curlevelnode，max，hashmap。头节点进队列，同时哈希表记录头节点的层数1。然后弹出，并且判断当前节点跟curlevel是不是一样，一样的话，curlevelnode++，如果不一样，那么更新max，同时curlevelnode=1.然后压入左孩子，右孩子以及对应的层数。
搜索二叉树：左边都比head小，右边都大。其实就是中序遍历判断是否降序。
完全二叉树：宽度优先遍历，如果cur有右无左，false，如果cur有左无右，leaf=true，然后判断如果leaf and 有左或右，那么false。
- 二叉树的递归套路
左数信息、右数信息，然后再判断。
搜索二叉树：lc98
用左右两个信息，把最小值最大值放入递归函数里，最小值最大值换成相应节点值。
二叉树的最近公共祖先：lc236
也可以用递归，如果root是空，p，q之中的话，返回root，否则，返回两边递归值（除非两边递归值都存在，就是pq分别在左右两边，返回root）
返回二叉树的后继节点：
后继节点是中序遍历的后面的值，其实就是，如果cur有右孩子，那就返回右孩子里最左的孩子，如果没有，就往上看，如果cur是父节点的左孩子，就返回父节点，否则一直往上走
二叉树的序列化和反序列化：
序列化：如果是空，返回#-，首先生成头节点-，然后左边递归、右边递归。
反序列化：把序列-用逗号分割，然后放到queue里，然后如果是#，返回空，head创立出来，然后左右分别递归。
折痕问题：
二叉树可以解决，每个折痕折一次，两边都会生成一个凸一个凹。所以用二叉树中序遍历就能生成上下顺序。