02.9.1.2 树与图高频 20 题
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.9 高频题单 / 02.9.1 高频题单与解题路线
本页为索引串联型题单:每题给出一句话思路、复杂度口径、易错点与本库关联页面,完整推导见关联页面。
02.9.1.2-001 二叉树层序遍历(LC 102)
一句话结论
BFS 按层扩展:队列存当前层节点,逐层记录出队节点值并把子节点入队。
概念解释
考点:队列 BFS;时间 O(n),空间 O(n)(队列宽度)。
原理流程
- 根入队。
- 按层大小出队收集值。
- 子节点入队。
代码 / 示例
关联:二叉树结构与递归遍历
常见误区
- 误区:不按层大小分批;正解:记录当前层队列长度,分层输出。
- 误区:子节点空指针入队。
追问
- Q:锯齿形层序(LC 103)? A:按层奇偶反转方向。
- Q:层序最右视图(LC 199)? A:每层取最后出队节点。
02.9.1.2-002 二叉树最大深度(LC 104)
一句话结论
递归:深度 = 1 + max(左子树深度, 右子树深度);空节点深度 0。
概念解释
考点:后序递归;时间 O(n),空间 O(h) 递归栈。
原理流程
- 空返回 0。
- 左右递归取大。
- 加一返回。
代码 / 示例
关联:二叉树结构与递归遍历
常见误区
- 误区:返回左右深度之和;正解:取较大者加一。
- 误区:迭代 BFS 层数计数口径错误。
追问
- Q:最小深度(LC 111)? A:需到最近叶子,单侧子树为空不能直接取 min。
- Q:迭代做法? A:BFS 按层计数到首个叶子。
02.9.1.2-003 翻转二叉树(LC 226)
一句话结论
前序递归:交换当前节点左右子树,再递归翻转两侧。
概念解释
考点:树递归变换;时间 O(n),空间 O(h)。
原理流程
- 空返回。
- 交换左右孩子。
- 递归翻转两侧。
代码 / 示例
关联:二叉树构造与变换
常见误区
- 误区:先递归再交换;正解:交换顺序不影响结果,但需保证两侧都被翻转。
- 误区:递归返回值未挂接。
追问
- Q:迭代做法? A:栈/队列遍历每个节点交换孩子。
- Q:与对称树判断区别? A:本题改结构,对称题比较两棵子树。
02.9.1.2-004 对称二叉树(LC 101)
一句话结论
递归比较两棵子树:左的左对右的右、左的右对右的左,值相等且结构对称。
概念解释
考点:双树递归;时间 O(n),空间 O(h)。
原理流程
- 两节点都空对称。
- 一空一非空不对称。
- 值相等再递归外侧与内侧。
代码 / 示例
关联:二叉树结构与递归遍历
常见误区
- 误区:只比较根左右值;正解:需逐层对称比较子树。
- 误区:内侧外侧配对写反。
追问
- Q:迭代做法? A:队列成对入队比较。
- Q:与翻转树关系? A:对称是自身镜像。
02.9.1.2-005 验证二叉搜索树(LC 98)
一句话结论
递归携带上下界:节点值必须在 (下界, 上界) 内,左子树上界为当前值,右子树下界为当前值。
概念解释
考点:BST 性质;时间 O(n),空间 O(h)。
原理流程
- 传 min、max 约束。
- 当前值越界返回 false。
- 递归左右收紧边界。
代码 / 示例
关联:BST 与平衡树
常见误区
- 误区:只比直接父子节点;正解:整棵左子树都要小于根。
- 误区:边界用相等值判断漏掉等于情况。
追问
- Q:中序遍历法? A:BST 中序严格递增,记录前值比对。
- Q:重复值怎么算合法? A:按题意,BST 通常不允许等值重复。
02.9.1.2-006 最近公共祖先(LC 236)
一句话结论
后序递归:左右子树分别查找 p、q;当前节点命中或两侧各找到一个,则当前为 LCA。
概念解释
考点:后序返回信息;时间 O(n),空间 O(h)。
原理流程
- 空返回 null。
- 命中 p/q 返回自身。
- 左右非空则当前为 LCA,否则返回非空一侧。
代码 / 示例
关联:二叉树结构与递归遍历
常见误区
- 误区:从上向下找路径再比对;正解:后序一次递归更直接。
- 误区:p、q 存在性未保证时返回 null 需区分。
追问
- Q:BST 版 LCA(LC 235)? A:利用大小关系向下走。
- Q:多叉树 LCA? A:同后序思路,聚合子节点结果。
02.9.1.2-007 二叉树直径(LC 543)
一句话结论
后序返回子树高度;经过当前节点的最长路径 = 左高 + 右高,全局更新最大直径。
概念解释
考点:树形 DP;时间 O(n),空间 O(h)。
原理流程
- 递归求高度。
- 每个节点算左右高度和。
- 全局取最大。
代码 / 示例
关联:树形 DP
常见误区
- 误区:直径等于树高;正解:直径是边数最长路径,可能不过根。
- 误区:返回值把直径与高度混淆。
追问
- Q:路径按节点数还是边数? A:题目口径不同,注意换算。
- Q:最大路径和(LC 124)? A:同框架,子树贡献取非负累加。
02.9.1.2-008 前序 + 中序构造二叉树(LC 105)
一句话结论
前序首元素为根,中序中定位根划分左右子树,递归按区间长度切分构造。
概念解释
考点:遍历序列还原;时间 O(n)(哈希定位中序),空间 O(h)。
原理流程
- 前序首为根。
- 哈希查中序根位置。
- 左右子树区间递归构造。
代码 / 示例
关联:二叉树构造与变换
常见误区
- 误区:左右子树在前序中的切分长度算错。
- 误区:中序定位用线性查找导致 O(n²)。
追问
- Q:中序 + 后序构造(LC 106)? A:后序末尾为根,其余对称切分。
- Q:无前序能唯一构造吗? A:仅中序不行,需另一种遍历。
02.9.1.2-009 BST 第 K 小元素(LC 230)
一句话结论
中序遍历 BST 得递增序列,数到第 K 个即答案;迭代中序可提前终止。
概念解释
考点:中序性质;时间 O(h+K),空间 O(h)。
原理流程
- 迭代中序压栈。
- 出队计数到 K。
- 返回当前节点值。
代码 / 示例
关联:BST 与平衡树
常见误区
- 误区:按层序排序取值;正解:中序天然有序。
- 误区:K 从 0 还是 1 计数口径错误。
追问
- Q:频繁查询第 K 小? A:节点维护子树大小,支持 O(h) 查询。
- Q:第 K 大? A:反中序(右根左)计数。
02.9.1.2-010 路径总和(LC 112)
一句话结论
DFS 递减剩余目标和,到叶子时判断剩余为 0;任一路径满足即返回。
概念解释
考点:树 DFS;时间 O(n),空间 O(h)。
原理流程
- 空返回 false。
- 叶子判断 sum == node.val。
- 左右递归扣减当前值。
代码 / 示例
关联:二叉树结构与递归遍历
常见误区
- 误区:非叶子节点就判断剩余为 0;正解:必须到叶子。
- 误区:左右结果未用或合并。
追问
- Q:路径总和 II(LC 113)? A:DFS 记录路径,叶子达标收集。
- Q:路径不一定从根开始(LC 437)? A:前缀和 + 两层递归。
02.9.1.2-011 Trie 前缀树实现(LC 208)
一句话结论
节点存子节点映射与结束标记;插入逐字符下沉,查找/前缀匹配沿字符走到底。
概念解释
考点:前缀树;插入/查询 O(L),空间 O(总字符)。
原理流程
- 数组/哈希存 26 个子节点。
- 插入逐字符建节点,末尾标记。
- 查询命中且结束标记为真。
代码 / 示例
关联:堆与 Trie 树
常见误区
- 误区:前缀匹配要求结束标记;正解:startsWith 只要求路径存在。
- 误区:共享前缀被重复存多份。
追问
- Q:Trie 与哈希存单词区别? A:Trie 支持前缀检索与公共前缀压缩。
- Q:单词搜索 II(LC 212)? A:Trie + 网格回溯剪枝。
02.9.1.2-012 岛屿数量(LC 200)
一句话结论
网格扫描,遇未访问陆地就 DFS/BFS 淹没整座岛,岛数加一;标记访问避免重复计数。
概念解释
考点:连通块搜索;时间 O(mn),空间 O(mn)(递归栈/队列)。
原理流程
- 遍历每格。
- 陆地则计数并 DFS 标记。
- 四方向扩展。
代码 / 示例
关联:岛屿与搜索类
常见误区
- 误区:只判上下左右漏掉越界检查。
- 误区:标记访问在回溯时撤销导致重复入队。
追问
- Q:最大岛屿面积(LC 695)? A:DFS 中累计面积取最大。
- Q:并查集做法? A:陆地合并连通分量,见 02.4.2.3。
02.9.1.2-013 课程表(LC 207)拓扑排序
一句话结论
建图统计入度,Kahn 队列剥离入度 0 节点;能处理完全部课程则无环可完成。
概念解释
考点:拓扑排序;时间 O(V+E),空间 O(V+E)。
原理流程
- 邻接表 + 入度表。
- 入度 0 入队。
- 剥离并减邻接入度,计数达 V 即可行。
代码 / 示例
关联:拓扑排序与环检测
常见误区
- 误区:有向边方向建反。
- 误区:剥离后未更新邻接入度。
追问
- Q:输出修课顺序(LC 210)? A:拓扑序列即答案。
- Q:DFS 判环做法? A:三色标记递归检测回边。
02.9.1.2-014 省份数量(LC 547)并查集
一句话结论
并查集合并有连接的城市,最终连通分量数即省份数;矩阵对称遍历避免重复合并。
概念解释
考点:并查集;时间 O(n² α(n)),空间 O(n)。
原理流程
- 初始化 n 个集合。
- 相连城市 union。
- 统计根节点个数。
代码 / 示例
关联:并查集
常见误区
- 误区:双重遍历重复合并无大碍但浪费。
- 误区:未做路径压缩/按秩合并导致退化。
追问
- Q:DFS/BFS 怎么做? A:扫描未访问城市扩散连通块。
- Q:并查集适合什么场景? A:动态连通性判断,无需完整图遍历。
02.9.1.2-015 单词接龙(LC 127)
一句话结论
BFS 按层扩展单词:每层变换可达的邻词,访问即标记;层数即最短转换长度。
概念解释
考点:BFS 最短路;时间 O(n·L·26) 量级,空间 O(n)。
原理流程
- 字典入集合,起点入队。
- 逐层枚举每位换字母找邻词。
- 命中终点返回层数。
代码 / 示例
关联:图表示与 DFS/BFS
常见误区
- 误区:DFS 求最短转换;正解:无权最短路径用 BFS。
- 误区:访问过的单词重复入队。
追问
- Q:双向 BFS? A:两端交替扩展,减小搜索层规模。
- Q:邻词怎么生成? A:逐位替换 26 字母查字典。
02.9.1.2-016 网络延迟时间(LC 743)
一句话结论
单源最短路:Dijkstra 松弛各节点,最大最短路距离即全网延迟;边权非负。
概念解释
考点:Dijkstra;时间 O(E log V),空间 O(V+E)。
原理流程
- 邻接表 + 距离表。
- 堆取最近未确定节点松弛。
- 不可达返回 -1,否则取最大距离。
代码 / 示例
关联:最短路径与最小生成树
常见误区
- 误区:边权为负仍用 Dijkstra;正解:负权需 Bellman-Ford。
- 误区:未判断存在不可达节点。
追问
- Q: Floyd-Warshall 适用? A:多源全配对,O(V³)。
- Q:堆中过期距离怎么处理? A:弹出时比对当前距离,过期跳过。
02.9.1.2-017 被围绕的区域(LC 130)
一句话结论
从边界上的 O 出发 DFS/BFS 标记所有连通 O(与外界连通),其余 O 改为 X,标记位还原。
概念解释
考点:反向洪水填充;时间 O(mn),空间 O(mn)。
原理流程
- 边界 O 扩散标记。
- 扫描全局:未标记 O 改 X。
- 标记位恢复。
代码 / 示例
关联:岛屿与搜索类
常见误区
- 误区:直接找内部 O 包围判断;正解:从边界反向标记更简单。
- 误区:扩散时把边界标记也改成 X。
追问
- Q:标记方式? A:临时改字符或访问矩阵。
- Q:与岛屿数量区别? A:本题只改不连通边界的区域。
02.9.1.2-018 腐烂橘子(LC 994)多源 BFS
一句话结论
所有腐烂橘子同时入队做 BFS,逐层扩散感染新鲜橘子;统计剩余新鲜数与扩散层数。
概念解释
考点:多源 BFS;时间 O(mn),空间 O(mn)。
原理流程
- 初始烂橘入队,统计新鲜数。
- 逐层感染,层数累加。
- 仍有新鲜返回 -1,否则返回层数。
代码 / 示例
关联:岛屿与搜索类
常见误区
- 误区:逐个烂橘单源 BFS;正解:多源同时起步才是最短扩散时间。
- 误区:层数与入队顺序口径混淆。
追问
- Q:为什么 BFS 而非 DFS? A:求最短扩散时间,无权图层序最短。
- Q:新鲜橘子为 0? A:返回 0。
02.9.1.2-019 克隆图(LC 133)
一句话结论
哈希存原节点→克隆节点;DFS/BFS 遍历原图,克隆节点并复制邻接表,避免重复克隆。
概念解释
考点:图遍历 + 哈希映射;时间 O(V+E),空间 O(V)。
原理流程
- 映射表记录已克隆。
- 遍历邻居,未克隆则递归克隆。
- 挂载克隆邻居。
代码 / 示例
关联:图表示与 DFS/BFS
常见误区
- 误区:无映射导致环图重复克隆死循环。
- 误区:克隆节点邻接表未复制完整。
追问
- Q:无向图环怎么处理? A:映射表命中即返回已克隆节点。
- Q:DFS 还是 BFS 都行? A:均可,关键是映射表去重。
02.9.1.2-020 冗余连接(LC 684)并查集
一句话结论
按边顺序并查集合并,两端已属同一集合的边即成环多余边,返回该边。
概念解释
考点:并查集成环检测;时间 O(E α(n)),空间 O(n)。
原理流程
- 初始化并查集。
- 逐条边查根。
- 同根即多余边,否则合并。
代码 / 示例
关联:并查集
常见误区
- 误区:返回成环的最后一条边之外的边;正解:题目要求输入顺序最后一条多余边。
- 误区:无向边合并方向写错。
追问
- Q:有向图冗余连接(LC 685)? A:需判入度与环,模型不同。
- Q:并查集记录边顺序? A:按输入顺序处理即可。