罗罗编程学习记录
本页内容 展开查看

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 为主;复杂度标注平均/最坏/均摊口径,不确定版本行为标注待确认。