二叉树的右视图
要点：层次遍历的套路
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public List<Integer> rightSideView(TreeNode root) { if(root == null){ return new ArrayList<>(); } //层次遍历 List<Integer> ans = new ArrayList<>(); Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size; i++){ TreeNode temp = queue.poll(); if(temp.left != null){ queue.offer(temp.left); } if(temp.right != null){ queue.offer(temp.right); } if(i == size -1){ ans.add(temp.val); } } } return ans; } }二叉树的层平均值
同上
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Double> ans = new ArrayList<>(); Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); double sum = 0; for(int i = 0; i < size; i++){ TreeNode temp = queue.poll(); sum += temp.val; if(temp.left != null){ queue.offer(temp.left); } if(temp.right != null){ queue.offer(temp.right); } } ans.add(sum/size); } return ans; } }二叉树的层序遍历
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { //队列 if(root == null){ return new ArrayList<>(); } Deque<TreeNode> deque = new ArrayDeque<>(); List<List<Integer>> anss = new ArrayList<>(); deque.offer(root); while(!deque.isEmpty()){ int size = deque.size(); List<Integer> ans = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode temp = deque.poll(); ans.add(temp.val); if(temp.left != null){ deque.offer(temp.left); } if(temp.right != null){ deque.offer(temp.right); } } anss.add(ans); } return anss; } }二叉树的锯齿形层序遍历
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { if(root == null){ return new ArrayList<>(); } //偶数反转 Deque<TreeNode> deque = new ArrayDeque<>(); List<List<Integer>> anss = new ArrayList<>(); //boolean isOuShu = false; deque.offer(root); while(!deque.isEmpty()){ int size = deque.size(); List<Integer> ans = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode temp = deque.poll(); ans.add(temp.val); if(temp.left != null){ deque.offer(temp.left); } if(temp.right != null){ deque.offer(temp.right); } } if(anss.size() % 2 > 0){ Collections.reverse(ans); } anss.add(ans); } return anss; } }二叉搜索树的最小绝对差
要点：中序遍历
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public int getMinimumDifference(TreeNode root) { //中序遍历 List<Integer> ans = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); //stack.push(root); while(!stack.isEmpty() || root != null){ while(root != null){ stack.push(root); root = root.left; } TreeNode temp = stack.pop(); ans.add(temp.val); root =temp.right ; } int minDiff = Integer.MAX_VALUE; for (int i = 1; i < ans.size(); i++) { minDiff = Math.min(minDiff, ans.get(i) - ans.get(i - 1)); } return minDiff; } }class Solution { public int getMinimumDifference(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; Integer prev = null; // 用 null 表示还没有前驱 int minDiff = Integer.MAX_VALUE; while (!stack.isEmpty() || cur != null) { // 一路向左 while (cur != null) { stack.push(cur); cur = cur.left; } // 访问当前节点 cur = stack.pop(); if (prev != null) { minDiff = Math.min(minDiff, cur.val - prev); } prev = cur.val; // 转向右子树 cur = cur.right; } return minDiff; } }二叉搜索树中第 K 小的元素
要点：中序遍历
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public int kthSmallest(TreeNode root, int k) { //中层遍历 Deque<TreeNode> stack = new ArrayDeque<>(); while(!stack.isEmpty() || root != null){ while(root != null){ stack.push(root); root = root.left; } TreeNode temp = stack.pop(); k--; if(k == 0){ return temp.val; } root = temp.right; } return 0; } }验证二叉搜索树
要点：中序遍历
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public boolean isValidBST(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); Double pre = -Double.MAX_VALUE; while(!stack.isEmpty() || root != null){ while(root != null){ stack.push(root); root = root.left; } TreeNode temp = stack.pop(); if(temp.val <= pre){ return false; } pre = (double)temp.val; root = temp.right; } return true; } }岛屿数量
要点：bfs
class Solution { public int numIslands(char[][] grid) { //bfs int ans = 0; int m = grid.length; int n = grid[0].length; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid[i][j] == '1'){ dfs(i, j, grid); ans++; } } } return ans; } public void dfs(int i, int j, char[][] grid){ if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'){ return; } grid[i][j] = '0'; dfs(i+1,j,grid); dfs(i-1,j,grid); dfs(i,j+1,grid); dfs(i,j-1,grid); } }随机知识
HashMap 1.7 vs 1.8 源码对比 + 画图文字描述 + 口述自测答案
一、底层结构核心差异
表格
| 维度 | JDK1.7 HashMap | JDK1.8 HashMap |
|---|---|---|
| 数组节点 | Entry<K,V>单向链表 | Node<K,V>单向链表 +TreeNode红黑树节点 |
| 链表插入 | 头插法（新节点放链表头部） | 尾插法（新节点追加到链表尾部） |
| 长链表优化 | 无优化，链表无限变长，查询 O (n) | 链表长度≥8 树化为红黑树，查询 O (logn)；≤6 退化为链表 |
| 扩容 rehash | 全部节点重新计算 hash，头插倒置链表 | 利用 hash 高位拆分高低链表，尾插保留原有顺序 |
二、为什么从 1.7 改成 1.8？两大核心原因
1. 头插法扩容并发死链（最关键改动动机）
1.7 头插法扩容逻辑
扩容时新建 2 倍长度数组，遍历原链表，每次把当前节点插到新链表头部，链表顺序完全反转。 并发场景下，两个线程同时触发扩容：
- 线程 A 遍历链表
A→B→null，刚处理完 A，时间片切走； - 线程 B 完整完成扩容，新链表变成
B→A→null； - 线程 A 恢复执行，继续拿 B 节点，头插后形成
A→B，B 的 next 又指向 A，环形链表； - 后续
get()、containsKey()遍历链表无限循环，CPU 100%。
1.8 尾插法解决死链
扩容时节点追加到高低链表尾部，原有节点相对顺序不变，不会倒置链表，并发扩容不会产生循环引用，彻底根除环形链表问题。
2. 长链表查询性能太差，引入红黑树优化
1.7 哈希冲突严重时，一条链表挂载几十上百节点，查询需要从头到尾遍历，时间复杂度 O (n)； 1.8 当链表过长转为红黑树，查找、插入、删除 O (logn)，大幅降低高冲突下查询耗时。
三、图文还原：1.7 环形链表形成过程（文字绘图，可直接手绘）
初始状态：原数组桶内链表A -> B -> null，扩容 newTab 长度翻倍
- 线程 A 执行 transfer，指针
e = A，next = B，还未迁移 A，被挂起； - 线程 B 完整执行扩容迁移：
- 迁移 B：newTab 链表
B - 迁移 A：头插到 B 前面，newTab 链表
A -> B -> null
- 迁移 B：newTab 链表
- 线程 A 恢复执行，当前 e=A，next=B：
- 将 A 头插入新链表：
A - e 更新为 next=B，B 不为 null，继续迁移 B
- B 的 next 原本是 null，但线程 B 已经把 B.next 指向 A
- 头插 B 到链表头部，得到
B -> A，A.next = B
- 将 A 头插入新链表：
- 最终形成环：
A ↔ B，无限循环
手绘简记：
plaintext
原始链表：A → B → null 线程B扩容后：A → B → null 线程A继续处理：B.next=A，A.next=B 环形闭环四、1.8 红黑树插入流程图（文字版手绘）
- 新 Node 计算 hash，定位数组下标桶
- 判断桶首节点：
- 桶为空：直接放数组，结束
- 桶不为空，key 相等：覆盖旧值，结束
- 桶是链表节点：
- 循环遍历链表尾部，同步统计链表长度
- 找到同 key 则覆盖；没找到则追加到链表尾部（尾插）
- 追加完成后，判断链表长度
len >= 8：执行treeifyBin()树化
- treeifyBin 流程：
- 判断数组长度是否小于 64：不树化，直接扩容（扩容打散冲突更高效）
- 链表节点转为 TreeNode 双向链表
- 双向链表构建红黑树，平衡染色、左旋右旋调整树结构
- 桶已经是红黑树根节点：
- 树中查找 key，匹配则覆盖
- 无匹配则插入新 TreeNode，自动平衡红黑树
流程图简化结构：
plaintext
计算hash定位桶 ↓ 桶空？→ 直接存入 ↓否 首节点key相等？→ 覆盖 ↓否 首节点是TreeNode？→ 红黑树插入+平衡 ↓否（普通链表） 遍历链表尾部尾插，计数长度 ↓ 长度≥8 && tab容量≥64 → 链表转红黑树 ↓ 长度≥8 && tab容量<64 → 扩容打散五、自测口述标准答案：为什么阈值是 8 转树、6 退链，不是 6 转树？
从概率、性能、红黑树开销三个层面解释：
哈希分布概率依据HashMap 默认 hash 扰动算法下，单个链表节点数量符合泊松分布。链表长度达到 8 的概率极低，仅千万分之一，正常业务几乎不会出现长链表；如果阈值设为 6，轻微哈希冲突就频繁树化，完全没必要。
树化 / 退树的开销平衡红黑树节点 TreeNode 比普通 Node 内存占用大很多，存储父、左右、颜色、前驱后继指针，维护平衡树还要左旋、右旋、染色，插入删除开销远高于普通链表。 如果阈值设 6，少量冲突就频繁转树，内存与计算开销陡增；等到链表长度到 8，线性遍历性能衰减已经非常明显，此时树化收益远大于开销。
6 作为退链阈值，防止频繁切换震荡树化阈值 8、退化阈值 6，中间留出差值缓冲。如果进树和退树阈值相同（比如都是 8），当链表节点在 8 个左右浮动时，会反复执行树化、退链，频繁转换结构造成性能抖动。设置 6 作为退化阈值，预留缓冲区间，避免频繁切换数据结构。
链表与红黑树查询性能拐点链表长度小于 8 时，顺序遍历的 CPU 缓存连续访问效率很高，O (n) 遍历速度并不慢；超过 8 个节点后，线性遍历耗时显著上升，红黑树 O (logn) 的优势才能体现出来，因此选择 8 作为树化临界点。
总结：8 是兼顾哈希概率、查询性能、结构转换开销的最优临界点，6 作为退化阈值缓冲，防止结构频繁震荡。
碎碎念：后续会更新每天学习的八股和算法 题，开始准备秋招的第46/7/8/9/50/【身体原因休息五天】51天。努力连续更新100天！以后每天就按，秋招项目【java +agent】，科研，必做项目，算法，八股，锻炼身体来总结。
总结：坚持，不管干什么都得坚持
1.算法面试150 97/150 2h
2.秋招项目，【java 项目】，
【agent 项目 】，
3.科研要跑一下，
4.检测项目，4h
6.背八股，
7.锻炼身体，
坚持，不完美也开始，坚定目标学习，心平气和。
