二叉树的右视图

要点：层次遍历的套路

/**
 * 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 倍长度数组，遍历原链表，每次把当前节点插到新链表头部，链表顺序完全反转。 并发场景下，两个线程同时触发扩容：

  1. 线程 A 遍历链表 A→B→null，刚处理完 A，时间片切走；
  2. 线程 B 完整完成扩容，新链表变成 B→A→null；
  3. 线程 A 恢复执行，继续拿 B 节点，头插后形成 A→B，B 的 next 又指向 A，环形链表；
  4. 后续get()、containsKey()遍历链表无限循环，CPU 100%。
1.8 尾插法解决死链

扩容时节点追加到高低链表尾部，原有节点相对顺序不变，不会倒置链表，并发扩容不会产生循环引用，彻底根除环形链表问题。

2. 长链表查询性能太差，引入红黑树优化

1.7 哈希冲突严重时，一条链表挂载几十上百节点，查询需要从头到尾遍历，时间复杂度 O (n)； 1.8 当链表过长转为红黑树，查找、插入、删除 O (logn)，大幅降低高冲突下查询耗时。

三、图文还原：1.7 环形链表形成过程（文字绘图，可直接手绘）

初始状态：原数组桶内链表 A -> B -> null，扩容 newTab 长度翻倍

  1. 线程 A 执行 transfer，指针 e = A，next = B，还未迁移 A，被挂起；
  2. 线程 B 完整执行扩容迁移：
    • 迁移 B：newTab 链表 B
    • 迁移 A：头插到 B 前面，newTab 链表 A -> B -> null
  3. 线程 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
  4. 最终形成环：A ↔ B，无限循环

手绘简记：

plaintext

原始链表：A → B → null
线程B扩容后：A → B → null
线程A继续处理：B.next=A，A.next=B  环形闭环

四、1.8 红黑树插入流程图（文字版手绘）

  1. 新 Node 计算 hash，定位数组下标桶
  2. 判断桶首节点：
    • 桶为空：直接放数组，结束
    • 桶不为空，key 相等：覆盖旧值，结束
  3. 桶是链表节点：
    • 循环遍历链表尾部，同步统计链表长度
    • 找到同 key 则覆盖；没找到则追加到链表尾部（尾插）
    • 追加完成后，判断链表长度 len >= 8：执行 treeifyBin() 树化
  4. treeifyBin 流程：
    1. 判断数组长度是否小于 64：不树化，直接扩容（扩容打散冲突更高效）
    2. 链表节点转为 TreeNode 双向链表
    3. 双向链表构建红黑树，平衡染色、左旋右旋调整树结构
  5. 桶已经是红黑树根节点：
    • 树中查找 key，匹配则覆盖
    • 无匹配则插入新 TreeNode，自动平衡红黑树

流程图简化结构：

plaintext

计算hash定位桶
    ↓
桶空？→ 直接存入
    ↓否
首节点key相等？→ 覆盖
    ↓否
首节点是TreeNode？→ 红黑树插入+平衡
    ↓否（普通链表）
遍历链表尾部尾插，计数长度
    ↓
长度≥8 && tab容量≥64 → 链表转红黑树
    ↓
长度≥8 && tab容量<64 → 扩容打散

五、自测口述标准答案：为什么阈值是 8 转树、6 退链，不是 6 转树？

从概率、性能、红黑树开销三个层面解释：

  1. 哈希分布概率依据 HashMap 默认 hash 扰动算法下，单个链表节点数量符合泊松分布。链表长度达到 8 的概率极低，仅千万分之一，正常业务几乎不会出现长链表；如果阈值设为 6，轻微哈希冲突就频繁树化，完全没必要。

  2. 树化 / 退树的开销平衡 红黑树节点 TreeNode 比普通 Node 内存占用大很多，存储父、左右、颜色、前驱后继指针，维护平衡树还要左旋、右旋、染色，插入删除开销远高于普通链表。 如果阈值设 6，少量冲突就频繁转树，内存与计算开销陡增；等到链表长度到 8，线性遍历性能衰减已经非常明显，此时树化收益远大于开销。

  3. 6 作为退链阈值，防止频繁切换震荡 树化阈值 8、退化阈值 6，中间留出差值缓冲。如果进树和退树阈值相同（比如都是 8），当链表节点在 8 个左右浮动时，会反复执行树化、退链，频繁转换结构造成性能抖动。设置 6 作为退化阈值，预留缓冲区间，避免频繁切换数据结构。

  4. 链表与红黑树查询性能拐点 链表长度小于 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.锻炼身体，

坚持，不完美也开始，坚定目标学习，心平气和。

# 面试 # 职场和发展 # 数据结构 # java # leetcode # 算法
Logo
亚马逊云科技技术品牌专区

更多推荐

2026年量化工具选择，要跟着能力基础走

读者应理解，选择工具前要先判断自己的能力基础和当前任务。工具应该帮助自己补上当前最关键的缺口，而不是替代学习顺序本身。

avatar 亚马逊云科技技术品牌专区

近期零基础学量化，先按基础差异拆学习顺序

读者应明白，拆解学习顺序时要先看自己的基础缺口，再决定哪一段需要放慢。不同流程阶段都有不同检查任务，学习路线要能反映这些差异。

avatar 亚马逊云科技技术品牌专区

最新零基础量化，先做可验证的小流程

读者应明白，先完成小而可验证的流程，比过早扩展功能更重要。只要小流程能够解释、运行和检查，就能为后续阶段的风险识别和假设确认打下基础。

avatar 亚马逊云科技技术品牌专区