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

02.9.1.2 树与图高频 20 题

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.9 高频题单 / 02.9.1 高频题单与解题路线

本页为索引串联型题单:每题给出一句话思路、复杂度口径、易错点与本库关联页面,完整推导见关联页面。

02.9.1.2-001 二叉树层序遍历(LC 102)

一句话结论

BFS 按层扩展:队列存当前层节点,逐层记录出队节点值并把子节点入队。

概念解释

考点:队列 BFS;时间 O(n),空间 O(n)(队列宽度)。

原理流程

  1. 根入队。
  2. 按层大小出队收集值。
  3. 子节点入队。

代码 / 示例

关联:二叉树结构与递归遍历

常见误区

  • 误区:不按层大小分批;正解:记录当前层队列长度,分层输出。
  • 误区:子节点空指针入队。

追问

  • Q:锯齿形层序(LC 103)? A:按层奇偶反转方向。
  • Q:层序最右视图(LC 199)? A:每层取最后出队节点。

02.9.1.2-002 二叉树最大深度(LC 104)

一句话结论

递归:深度 = 1 + max(左子树深度, 右子树深度);空节点深度 0。

概念解释

考点:后序递归;时间 O(n),空间 O(h) 递归栈。

原理流程

  1. 空返回 0。
  2. 左右递归取大。
  3. 加一返回。

代码 / 示例

关联:二叉树结构与递归遍历

常见误区

  • 误区:返回左右深度之和;正解:取较大者加一。
  • 误区:迭代 BFS 层数计数口径错误。

追问

  • Q:最小深度(LC 111)? A:需到最近叶子,单侧子树为空不能直接取 min。
  • Q:迭代做法? A:BFS 按层计数到首个叶子。

02.9.1.2-003 翻转二叉树(LC 226)

一句话结论

前序递归:交换当前节点左右子树,再递归翻转两侧。

概念解释

考点:树递归变换;时间 O(n),空间 O(h)。

原理流程

  1. 空返回。
  2. 交换左右孩子。
  3. 递归翻转两侧。

代码 / 示例

关联:二叉树构造与变换

常见误区

  • 误区:先递归再交换;正解:交换顺序不影响结果,但需保证两侧都被翻转。
  • 误区:递归返回值未挂接。

追问

  • Q:迭代做法? A:栈/队列遍历每个节点交换孩子。
  • Q:与对称树判断区别? A:本题改结构,对称题比较两棵子树。

02.9.1.2-004 对称二叉树(LC 101)

一句话结论

递归比较两棵子树:左的左对右的右、左的右对右的左,值相等且结构对称。

概念解释

考点:双树递归;时间 O(n),空间 O(h)。

原理流程

  1. 两节点都空对称。
  2. 一空一非空不对称。
  3. 值相等再递归外侧与内侧。

代码 / 示例

关联:二叉树结构与递归遍历

常见误区

  • 误区:只比较根左右值;正解:需逐层对称比较子树。
  • 误区:内侧外侧配对写反。

追问

  • Q:迭代做法? A:队列成对入队比较。
  • Q:与翻转树关系? A:对称是自身镜像。

02.9.1.2-005 验证二叉搜索树(LC 98)

一句话结论

递归携带上下界:节点值必须在 (下界, 上界) 内,左子树上界为当前值,右子树下界为当前值。

概念解释

考点:BST 性质;时间 O(n),空间 O(h)。

原理流程

  1. 传 min、max 约束。
  2. 当前值越界返回 false。
  3. 递归左右收紧边界。

代码 / 示例

关联:BST 与平衡树

常见误区

  • 误区:只比直接父子节点;正解:整棵左子树都要小于根。
  • 误区:边界用相等值判断漏掉等于情况。

追问

  • Q:中序遍历法? A:BST 中序严格递增,记录前值比对。
  • Q:重复值怎么算合法? A:按题意,BST 通常不允许等值重复。

02.9.1.2-006 最近公共祖先(LC 236)

一句话结论

后序递归:左右子树分别查找 p、q;当前节点命中或两侧各找到一个,则当前为 LCA。

概念解释

考点:后序返回信息;时间 O(n),空间 O(h)。

原理流程

  1. 空返回 null。
  2. 命中 p/q 返回自身。
  3. 左右非空则当前为 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)。

原理流程

  1. 递归求高度。
  2. 每个节点算左右高度和。
  3. 全局取最大。

代码 / 示例

关联:树形 DP

常见误区

  • 误区:直径等于树高;正解:直径是边数最长路径,可能不过根。
  • 误区:返回值把直径与高度混淆。

追问

  • Q:路径按节点数还是边数? A:题目口径不同,注意换算。
  • Q:最大路径和(LC 124)? A:同框架,子树贡献取非负累加。

02.9.1.2-008 前序 + 中序构造二叉树(LC 105)

一句话结论

前序首元素为根,中序中定位根划分左右子树,递归按区间长度切分构造。

概念解释

考点:遍历序列还原;时间 O(n)(哈希定位中序),空间 O(h)。

原理流程

  1. 前序首为根。
  2. 哈希查中序根位置。
  3. 左右子树区间递归构造。

代码 / 示例

关联:二叉树构造与变换

常见误区

  • 误区:左右子树在前序中的切分长度算错。
  • 误区:中序定位用线性查找导致 O(n²)。

追问

  • Q:中序 + 后序构造(LC 106)? A:后序末尾为根,其余对称切分。
  • Q:无前序能唯一构造吗? A:仅中序不行,需另一种遍历。

02.9.1.2-009 BST 第 K 小元素(LC 230)

一句话结论

中序遍历 BST 得递增序列,数到第 K 个即答案;迭代中序可提前终止。

概念解释

考点:中序性质;时间 O(h+K),空间 O(h)。

原理流程

  1. 迭代中序压栈。
  2. 出队计数到 K。
  3. 返回当前节点值。

代码 / 示例

关联: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)。

原理流程

  1. 空返回 false。
  2. 叶子判断 sum == node.val。
  3. 左右递归扣减当前值。

代码 / 示例

关联:二叉树结构与递归遍历

常见误区

  • 误区:非叶子节点就判断剩余为 0;正解:必须到叶子。
  • 误区:左右结果未用或合并。

追问

  • Q:路径总和 II(LC 113)? A:DFS 记录路径,叶子达标收集。
  • Q:路径不一定从根开始(LC 437)? A:前缀和 + 两层递归。

02.9.1.2-011 Trie 前缀树实现(LC 208)

一句话结论

节点存子节点映射与结束标记;插入逐字符下沉,查找/前缀匹配沿字符走到底。

概念解释

考点:前缀树;插入/查询 O(L),空间 O(总字符)。

原理流程

  1. 数组/哈希存 26 个子节点。
  2. 插入逐字符建节点,末尾标记。
  3. 查询命中且结束标记为真。

代码 / 示例

关联:堆与 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)(递归栈/队列)。

原理流程

  1. 遍历每格。
  2. 陆地则计数并 DFS 标记。
  3. 四方向扩展。

代码 / 示例

关联:岛屿与搜索类

常见误区

  • 误区:只判上下左右漏掉越界检查。
  • 误区:标记访问在回溯时撤销导致重复入队。

追问

  • 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)。

原理流程

  1. 邻接表 + 入度表。
  2. 入度 0 入队。
  3. 剥离并减邻接入度,计数达 V 即可行。

代码 / 示例

关联:拓扑排序与环检测

常见误区

  • 误区:有向边方向建反。
  • 误区:剥离后未更新邻接入度。

追问

  • Q:输出修课顺序(LC 210)? A:拓扑序列即答案。
  • Q:DFS 判环做法? A:三色标记递归检测回边。

02.9.1.2-014 省份数量(LC 547)并查集

一句话结论

并查集合并有连接的城市,最终连通分量数即省份数;矩阵对称遍历避免重复合并。

概念解释

考点:并查集;时间 O(n² α(n)),空间 O(n)。

原理流程

  1. 初始化 n 个集合。
  2. 相连城市 union。
  3. 统计根节点个数。

代码 / 示例

关联:并查集

常见误区

  • 误区:双重遍历重复合并无大碍但浪费。
  • 误区:未做路径压缩/按秩合并导致退化。

追问

  • Q:DFS/BFS 怎么做? A:扫描未访问城市扩散连通块。
  • Q:并查集适合什么场景? A:动态连通性判断,无需完整图遍历。

02.9.1.2-015 单词接龙(LC 127)

一句话结论

BFS 按层扩展单词:每层变换可达的邻词,访问即标记;层数即最短转换长度。

概念解释

考点:BFS 最短路;时间 O(n·L·26) 量级,空间 O(n)。

原理流程

  1. 字典入集合,起点入队。
  2. 逐层枚举每位换字母找邻词。
  3. 命中终点返回层数。

代码 / 示例

关联:图表示与 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. 邻接表 + 距离表。
  2. 堆取最近未确定节点松弛。
  3. 不可达返回 -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)。

原理流程

  1. 边界 O 扩散标记。
  2. 扫描全局:未标记 O 改 X。
  3. 标记位恢复。

代码 / 示例

关联:岛屿与搜索类

常见误区

  • 误区:直接找内部 O 包围判断;正解:从边界反向标记更简单。
  • 误区:扩散时把边界标记也改成 X。

追问

  • Q:标记方式? A:临时改字符或访问矩阵。
  • Q:与岛屿数量区别? A:本题只改不连通边界的区域。

02.9.1.2-018 腐烂橘子(LC 994)多源 BFS

一句话结论

所有腐烂橘子同时入队做 BFS,逐层扩散感染新鲜橘子;统计剩余新鲜数与扩散层数。

概念解释

考点:多源 BFS;时间 O(mn),空间 O(mn)。

原理流程

  1. 初始烂橘入队,统计新鲜数。
  2. 逐层感染,层数累加。
  3. 仍有新鲜返回 -1,否则返回层数。

代码 / 示例

关联:岛屿与搜索类

常见误区

  • 误区:逐个烂橘单源 BFS;正解:多源同时起步才是最短扩散时间。
  • 误区:层数与入队顺序口径混淆。

追问

  • Q:为什么 BFS 而非 DFS? A:求最短扩散时间,无权图层序最短。
  • Q:新鲜橘子为 0? A:返回 0。

02.9.1.2-019 克隆图(LC 133)

一句话结论

哈希存原节点→克隆节点;DFS/BFS 遍历原图,克隆节点并复制邻接表,避免重复克隆。

概念解释

考点:图遍历 + 哈希映射;时间 O(V+E),空间 O(V)。

原理流程

  1. 映射表记录已克隆。
  2. 遍历邻居,未克隆则递归克隆。
  3. 挂载克隆邻居。

代码 / 示例

关联:图表示与 DFS/BFS

常见误区

  • 误区:无映射导致环图重复克隆死循环。
  • 误区:克隆节点邻接表未复制完整。

追问

  • Q:无向图环怎么处理? A:映射表命中即返回已克隆节点。
  • Q:DFS 还是 BFS 都行? A:均可,关键是映射表去重。

02.9.1.2-020 冗余连接(LC 684)并查集

一句话结论

按边顺序并查集合并,两端已属同一集合的边即成环多余边,返回该边。

概念解释

考点:并查集成环检测;时间 O(E α(n)),空间 O(n)。

原理流程

  1. 初始化并查集。
  2. 逐条边查根。
  3. 同根即多余边,否则合并。

代码 / 示例

关联:并查集

常见误区

  • 误区:返回成环的最后一条边之外的边;正解:题目要求输入顺序最后一条多余边。
  • 误区:无向边合并方向写错。

追问

  • Q:有向图冗余连接(LC 685)? A:需判入度与环,模型不同。
  • Q:并查集记录边顺序? A:按输入顺序处理即可。