第八章 字典树:前缀的力量
**面试突击 · 字典树。** 从标准 Trie 到压缩 Trie (Radix Tree),手写插入/查找/前缀匹配的完整实现,剖析数组 vs 哈希两种子节点存储的工程取舍,掌握单词搜索 II、自动补全设计等高频面试题,深入游戏敏感词过滤与控制台命令补全实战。
第九章 并查集:找老大
**面试突击 · 并查集。** 从 Quick Find 到 Quick Union,手写路径压缩 + 按秩合并的终极实现,剖析 α(n) 反阿克曼函数的近 O(1) 复杂度,掌握连通分量、冗余连接、账户合并等高频面试题,深入游戏地图连通验证与公会合并实战。
7.2 最短路径:Dijkstra & A*
**面试突击 · 最短路径。** 从 Dijkstra 的贪心策略到 Bellman-Ford 的负权处理,从 Floyd-Warshall 的全源 DP 到 A* 的启发式搜索,掌握图中「找最优路径」的四大核心算法,附游戏寻路实战。
7.3 最小生成树 & 拓扑排序
**面试突击 · MST & 拓扑排序。** Kruskal 贪心选边 + 并查集、Prim 贪心扩点 + 最小堆,掌握最小代价连通;Kahn BFS 入度法 + DFS 后序翻转,掌握 DAG 的依赖排序。附技能树、地图生成、资源加载等游戏实战场景。
第七章 图:万物皆可连
**面试突击 · 图(总览)。** 图是最通用的数据结构——社交网络、地图导航、任务依赖、网络拓扑,一切「关系」都可以用图建模。本章拆分为三个子章节:图的表示与遍历、最短路径与 A* 寻路、最小生成树与拓扑排序。
6.1 二叉树基础与遍历
**面试突击 · 二叉树。** 从树的基本术语到四种遍历(递归/迭代/Morris),涵盖最大深度、对称性判断、翻转二叉树、路径总和、最近公共祖先、序列化等 15+ 道高频面试题的完整解析。
6.2 二叉搜索树 BST
**面试突击 · BST。** 从二叉搜索树的有序性质到增删查的完整 C++ 实现,剖析 BST 退化问题与 std::map/std::set 的选型原因,手撕验证 BST、第 K 小元素、删除节点等高频面试题。