2022.4.22
链表刷题：
哈希表刷题：
- 242. 有效的字母异位词 数组
- 349. 两个数组的交集 HashSet
- 202. 快乐数 HashSet
- 1. 两数之和 HashMap
- 454. 四数相加 II HashMap
1和454都是用目标数与某数相减的值代入HashMap中。
理论知识：哈希表理论基础
总结：
- 一般来说哈希表都是用来快速判断一个元素是否出现集合里。
- 对于哈希表，要知道哈希函数和哈希碰撞在哈希表中的作用.
哈希函数是把传入的key映射到符号表的索引上。
哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。 - 三种哈希结构：
- 数组
- HashSet
- HashMap
- 什么时候使用数组做哈希表？ 数组就是简单的哈希表，但是数组的大小是受限的！题目包含小写字母，那么使用数组来做哈希最合适不过。
- 什么时候使用HashSet做哈希表？ 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。那就考虑HashSet。
- 什么时候使用HashMap做哈希表？ 同时存放两个元素，且两个元素有对应关系。
二叉树刷题：
二叉树的递归遍历三要素：
1、确定递归函数的参数和返回值
2、确定终止条件
3、确定单层递归的逻辑
理论知识： 二叉树基础篇 ：
- 二叉树（没有值）
- 满二叉树
- 完全二叉树
- 二叉搜索树（有序树）
- 平衡二叉搜索树（它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。）
- 二叉树的存储方式（一般用链式存储）
- 链式存储
- 顺序存储
- 二叉树的遍历方式
- 深度优先遍历（先往深走，遇到叶子节点再往回走）
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历 （一层一层的去遍历）
- 层次遍历（迭代法）
- 深度优先遍历（先往深走，遇到叶子节点再往回走）
- 节点定义：（TreeNode）
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
