树与图

树是面试重灾区：二叉树遍历是手写代码基础，红黑树、B+ 树则考察你对"为什么数据库/容器选这种树"的理解。

Q1: 二叉树的前中后序遍历，递归和迭代怎么写？ 「🟢 校招/初级」

考察点：递归思维 + 用栈模拟递归的能力。

参考答案：

• 前序：根→左→右；中序：左→根→右；后序：左→右→根。
• 递归版三行代码，区别只是根节点访问位置。
• 迭代版用显式栈：中序遍历模板是"一路向左压栈，弹出时访问并转向右子树"；后序最麻烦，常用"根右左"遍历后反转结果。
• 层序遍历用队列（BFS）。

// 中序遍历迭代模板
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
    while (cur != null) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    // 访问 cur.val
    cur = cur.right;
}

追问延伸：

• 已知前序 + 中序怎么重建二叉树？
• 为什么后序不能只靠"前序+后序"唯一重建？

Q2: 二叉搜索树有什么问题？怎么解决？ 「🟡 中级」

考察点：从朴素结构到平衡树的演进逻辑。

参考答案：

• BST 左小右大，中序遍历有序；但顺序插入会退化成链表，查找变 O(n)。
• 解决方案是平衡树：AVL 严格平衡（左右子树高度差 ≤1），查找快但旋转频繁；红黑树 弱平衡（最长路径不超过最短的 2 倍），增删查综合性能好，是 Java TreeMap、C++ map 的选择。

追问延伸：

• 红黑树的五条性质能背出来吗？
• 为什么 JDK 选红黑树而不是 AVL？

Q3: 为什么 MySQL InnoDB 用 B+ 树而不是红黑树或哈希表？ 「🟡 中级」

考察点：索引结构选型的经典综合题。

参考答案：

• 磁盘因素：数据库数据在磁盘上，优化目标是最少 IO 次数。B+ 树是多叉树，节点大小对齐磁盘页（16KB），3~4 层就能存千万级数据，一次查询 3~4 次 IO。
• 对比红黑树：二叉树太高，IO 次数多。
• 对比哈希：哈希只支持等值查询，不支持范围查询和排序。
• B+ 树非叶子节点不存数据只存键，一页能放更多索引项；叶子节点用链表串联，范围查询高效。

追问延伸：

• 聚簇索引和二级索引在 B+ 树上的区别？
• 为什么推荐自增主键？（页分裂）

Q4: 图的遍历有哪些？最短路径算法怎么选？ 「🟡 中级」

考察点：图的存储与经典算法。

参考答案：

• 存储：邻接矩阵（稠密图，O(V²) 空间）、邻接表（稀疏图）。
• 遍历：BFS 用队列，可求无权图最短路；DFS 用栈/递归，可判环、拓扑排序。
• 最短路：
  • Dijkstra：单源、非负权，堆优化后 O(E log V)。
  • Bellman-Ford：支持负权边，可判负环。
  • Floyd：多源，O(V³)，适合小规模。

追问延伸：

• 怎么判断有向图有没有环？（DFS 三色标记 / 拓扑排序）
• 为什么 Dijkstra 不能处理负权边？

Q5: 什么是并查集？ 「🟡 中级」

考察点：连通性问题的常用工具。

参考答案：

• 用数组表示森林，每个元素指向父节点；find 查根、union 合并两棵树。
• 两个优化：路径压缩（find 时把节点直接挂到根）+ 按秩合并（小树挂大树），均摊复杂度接近 O(1)。
• 应用：连通分量计数、Kruskal 最小生成树、判断冗余连接。

追问延伸：

• 路径压缩为什么不能和按秩合并简单叠加时的复杂度分析？
• 朋友圈问题怎么用并查集解？

Q6: 前缀树（Trie）的应用场景？ 「🟡 中级」

考察点：面向字符串场景的数据结构储备。

参考答案：

• 按字符分层的多叉树，公共前缀共享路径；插入和查询都是 O(L)（L 为串长）。
• 应用：搜索框自动补全、拼写检查、IP 路由（最长前缀匹配）、敏感词过滤。
• 缺点：字符集大时内存开销高，可用压缩前缀树（Radix Tree）优化，Redis 集群的 slot 路由也用了类似结构。

追问延伸：

• 怎么在 Trie 上实现"模糊匹配"？
• Trie 和哈希表存字符串相比各有什么优劣？