02.4 树与图
所属:全栈开发面试题库 / 02 数据结构与算法
覆盖范围
- 二叉树结构、前中后序递归/迭代、层序、Morris、深度/平衡/直径/路径和
- BST 查找/插入/删除、区间验证、中序有序、第 K 小、前驱后继、AVL 与红黑树概念
- 二叉树构造与变换:序列重建、翻转、对称、合并、拉平、序列化、普通树 LCA
- 堆与 Trie:上浮下沉、建堆 O(n)、Top-K、前缀树插入/查询/前缀匹配
- 图表示与 DFS/BFS、连通分量、二分图、克隆图、多源 BFS
- 拓扑排序与环检测:Kahn、DFS 逆后序、三色判环、课程表
- 并查集:路径压缩、按秩合并、连通分量、冗余连接、等式判定
- 最短路径与最小生成树:BFS、Dijkstra、Bellman-Ford、Floyd、Kruskal、Prim
子主题
| 编号 | 主题 | 覆盖范围 |
|---|---|---|
| 02.4.1 | 二叉树与遍历 | 4 个子主题 80 题:二叉树结构与递归遍历、BST 与平衡树、构造与变换、堆与 Trie 树 |
| 02.4.2 | 图论与并查集 | 4 个子主题 80 题:图表示与 DFS/BFS、拓扑排序与环检测、并查集、最短路径与最小生成树 |
面试题索引
| 编号 | 题目 | 难度 | 频率 | 所在页面 |
|---|---|---|---|---|
| 02.4.1.1-010 | 层序遍历(BFS) | 中等 | ★★★★★ | 二叉树结构与递归遍历 |
| 02.4.1.1-012 | 二叉树最大深度(LC 104) | 简单 | ★★★★★ | 二叉树结构与递归遍历 |
| 02.4.1.1-014 | 二叉树直径(LC 543) | 简单 | ★★★★☆ | 二叉树结构与递归遍历 |
| 02.4.1.2-005 | 验证 BST(LC 98) | 中等 | ★★★★★ | BST 与平衡树 |
| 02.4.1.2-007 | BST 最近公共祖先(LC 235) | 简单 | ★★★★☆ | BST 与平衡树 |
| 02.4.1.2-009 | BST 第 K 小元素(LC 230) | 中等 | ★★★★☆ | BST 与平衡树 |
| 02.4.1.3-001 | 前序 + 中序构造二叉树(LC 105) | 中等 | ★★★★☆ | 二叉树构造与变换 |
| 02.4.1.3-005 | 对称二叉树(LC 101) | 简单 | ★★★★☆ | 二叉树构造与变换 |
| 02.4.1.3-009 | 序列化与反序列化(LC 297) | 困难 | ★★★★☆ | 二叉树构造与变换 |
| 02.4.1.3-012 | 普通二叉树最近公共祖先(LC 236) | 中等 | ★★★★★ | 二叉树构造与变换 |
| 02.4.1.4-007 | Top-K 用堆选择方向 | 中等 | ★★★★★ | 堆与 Trie 树 |
| 02.4.1.4-009 | Trie 插入 | 中等 | ★★★★☆ | 堆与 Trie 树 |
| 02.4.2.1-010 | 岛屿数量(LC 200) | 中等 | ★★★★★ | 图表示与 DFS/BFS |
| 02.4.2.1-012 | 判断二分图(LC 785) | 中等 | ★★★★☆ | 图表示与 DFS/BFS |
| 02.4.2.1-015 | 腐烂橘子(LC 994)多源 BFS | 中等 | ★★★★☆ | 图表示与 DFS/BFS |
| 02.4.2.2-005 | 课程表 I(LC 207) | 中等 | ★★★★★ | 拓扑排序与环检测 |
| 02.4.2.2-006 | 课程表 II(LC 210) | 中等 | ★★★★☆ | 拓扑排序与环检测 |
| 02.4.2.3-008 | 省份数量(LC 547) | 中等 | ★★★★☆ | 并查集 |
| 02.4.2.3-009 | 冗余连接(LC 684) | 中等 | ★★★★☆ | 并查集 |
| 02.4.2.4-004 | Dijkstra 堆实现 | 中等 | ★★★★★ | 最短路径与最小生成树 |
| 02.4.2.4-010 | Kruskal 最小生成树 | 中等 | ★★★★☆ | 最短路径与最小生成树 |
| 02.4.2.4-014 | 网络延迟时间(LC 743) | 中等 | ★★★★☆ | 最短路径与最小生成树 |
当前状态
- 02.4.1 已完成 4 个子主题、80 题;02.4.2 已完成 4 个子主题、80 题,合计 160 题,全部为可学习型详解。
- 页面结构:知识域首页 + 子主题页 + 分册 TOC 三层登记。
- 代码以 Java 为主;复杂度标注平均/最坏/均摊口径,不确定版本行为标注待确认。