depth-first-search.md

深度优先搜索

全部标签

数据结构

数组 矩阵 链表 双向链表 栈 单调栈 队列 单调队列 堆（优先队列） 哈希表 字符串 字符串匹配 树 二叉树 二叉搜索树 最小生成树 图 有序集合 拓扑排序 最短路 强连通分量 欧拉回路 双连通分量 并查集 字典树 线段树 树状数组 后缀数组

算法

枚举 递归 分治 回溯 贪心 动态规划 排序 桶排序 计数排序 基数排序 归并排序 快速选择 二分查找 记忆化搜索 深度优先搜索 广度优先搜索 双指针 位运算 前缀和 计数 滑动窗口 状态压缩 哈希函数 滚动哈希 扫描线

其他

数学 数论 几何 博弈 模拟 组合数学 随机化 概率与统计 水塘抽样 拒绝采样 数据库 设计 数据流 脑筋急转弯 交互 迭代器 多线程

---

题号	标题	题解	标签	难度	力扣
94	二叉树的中序遍历	[✓]	栈 树 深度优先搜索 1+	🟢	🀄️ 🔗
98	验证二叉搜索树	[✓]	树 深度优先搜索 二叉搜索树 1+	🟠	🀄️ 🔗
99	恢复二叉搜索树	[✓]	树 深度优先搜索 二叉搜索树 1+	🟠	🀄️ 🔗
100	相同的树	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
101	对称二叉树	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
104	二叉树的最大深度	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
110	平衡二叉树	[✓]	树 深度优先搜索 二叉树	🟢	🀄️ 🔗
111	二叉树的最小深度	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
112	路径总和	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
113	路径总和 II	[✓]	树 深度优先搜索 回溯 1+	🟠	🀄️ 🔗
114	二叉树展开为链表	[✓]	栈 树 深度优先搜索 2+	🟠	🀄️ 🔗
116	填充每个节点的下一个右侧节点指针	[✓]	树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗
117	填充每个节点的下一个右侧节点指针 II	[✓]	树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗
124	二叉树中的最大路径和	[✓]	树 深度优先搜索 动态规划 1+	🔴	🀄️ 🔗
129	求根节点到叶节点数字之和	[✓]	树 深度优先搜索 二叉树	🟠	🀄️ 🔗
130	被围绕的区域	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
133	克隆图	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
144	二叉树的前序遍历	[✓]	栈 树 深度优先搜索 1+	🟢	🀄️ 🔗
145	二叉树的后序遍历	[✓]	栈 树 深度优先搜索 1+	🟢	🀄️ 🔗
156	上下翻转二叉树 🔒	[✓]	树 深度优先搜索 二叉树	🟠	🀄️ 🔗
199	二叉树的右视图	[✓]	树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
200	岛屿数量	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
207	课程表	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
210	课程表 II	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
211	添加与搜索单词 - 数据结构设计	[✓]	深度优先搜索 设计 字典树 1+	🟠	🀄️ 🔗
226	翻转二叉树	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
230	二叉搜索树中第 K 小的元素	[✓]	树 深度优先搜索 二叉搜索树 1+	🟠	🀄️ 🔗
235	二叉搜索树的最近公共祖先	[✓]	树 深度优先搜索 二叉搜索树 1+	🟠	🀄️ 🔗
236	二叉树的最近公共祖先	[✓]	树 深度优先搜索 二叉树	🟠	🀄️ 🔗
250	统计同值子树 🔒		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
257	二叉树的所有路径	[✓]	树 深度优先搜索 字符串 2+	🟢	🀄️ 🔗
261	以图判树 🔒		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
269	火星词典 🔒		深度优先搜索 广度优先搜索 图 3+	🔴	🀄️ 🔗
270	最接近的二叉搜索树值 🔒		树 深度优先搜索 二叉搜索树 2+	🟢	🀄️ 🔗
272	最接近的二叉搜索树值 II 🔒		栈 树 深度优先搜索 4+	🔴	🀄️ 🔗
285	二叉搜索树中的中序后继 🔒		树 深度优先搜索 二叉搜索树 1+	🟠	🀄️ 🔗
297	二叉树的序列化与反序列化	[✓]	树 深度优先搜索 广度优先搜索 3+	🔴	🀄️ 🔗
298	二叉树最长连续序列 🔒		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
302	包含全部黑色像素的最小矩形 🔒		深度优先搜索 广度优先搜索 数组 2+	🔴	🀄️ 🔗
310	最小高度树	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
314	二叉树的垂直遍历 🔒		树 深度优先搜索 广度优先搜索 3+	🟠	🀄️ 🔗
323	无向图中连通分量的数目 🔒		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
329	矩阵中的最长递增路径	[✓]	深度优先搜索 广度优先搜索 图 5+	🔴	🀄️ 🔗
332	重新安排行程		深度优先搜索 图 欧拉回路	🔴	🀄️ 🔗
333	最大二叉搜索子树 🔒		树 深度优先搜索 二叉搜索树 2+	🟠	🀄️ 🔗
337	打家劫舍 III	[✓]	树 深度优先搜索 动态规划 1+	🟠	🀄️ 🔗
339	嵌套列表加权和 🔒		深度优先搜索 广度优先搜索	🟠	🀄️ 🔗
341	扁平化嵌套列表迭代器	[✓]	栈 树 深度优先搜索 3+	🟠	🀄️ 🔗
364	嵌套列表加权和 II 🔒		栈 深度优先搜索 广度优先搜索	🟠	🀄️ 🔗
365	水壶问题	[✓]	深度优先搜索 广度优先搜索 数学	🟠	🀄️ 🔗
366	寻找二叉树的叶子节点 🔒	[✓]	树 深度优先搜索 二叉树	🟠	🀄️ 🔗
385	迷你语法分析器	[✓]	栈 深度优先搜索 字符串	🟠	🀄️ 🔗
386	字典序排数	[✓]	深度优先搜索 字典树	🟠	🀄️ 🔗
388	文件的最长绝对路径	[✓]	栈 深度优先搜索 字符串	🟠	🀄️ 🔗
399	除法求值	[✓]	深度优先搜索 广度优先搜索 并查集 4+	🟠	🀄️ 🔗
404	左叶子之和	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
417	太平洋大西洋水流问题	[✓]	深度优先搜索 广度优先搜索 数组 1+	🟠	🀄️ 🔗
419	棋盘上的战舰	[✓]	深度优先搜索 数组 矩阵	🟠	🀄️ 🔗
426	将二叉搜索树转化为排序的双向链表 🔒	[✓]	栈 树 深度优先搜索 4+	🟠	🀄️ 🔗
428	序列化和反序列化 N 叉树 🔒		树 深度优先搜索 广度优先搜索 1+	🔴	🀄️ 🔗
430	扁平化多级双向链表	[✓]	深度优先搜索 链表 双向链表	🟠	🀄️ 🔗
431	将 N 叉树编码为二叉树 🔒		树 深度优先搜索 广度优先搜索 2+	🔴	🀄️ 🔗
437	路径总和 III	[✓]	树 深度优先搜索 二叉树	🟠	🀄️ 🔗
449	序列化和反序列化二叉搜索树	[✓]	树 深度优先搜索 广度优先搜索 4+	🟠	🀄️ 🔗
463	岛屿的周长	[✓]	深度优先搜索 广度优先搜索 数组 1+	🟢	🀄️ 🔗
472	连接词		深度优先搜索 字典树 数组 2+	🔴	🀄️ 🔗
490	迷宫 🔒		深度优先搜索 广度优先搜索 数组 1+	🟠	🀄️ 🔗
499	迷宫 III 🔒		深度优先搜索 广度优先搜索 图 5+	🔴	🀄️ 🔗
501	二叉搜索树中的众数	[✓]	树 深度优先搜索 二叉搜索树 1+	🟢	🀄️ 🔗
505	迷宫 II 🔒		深度优先搜索 广度优先搜索 图 4+	🟠	🀄️ 🔗
508	出现次数最多的子树元素和		树 深度优先搜索 哈希表 1+	🟠	🀄️ 🔗
513	找树左下角的值		树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
514	自由之路	[✓]	深度优先搜索 广度优先搜索 字符串 1+	🔴	🀄️ 🔗
515	在每个树行中找最大值	[✓]	树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
529	扫雷游戏		深度优先搜索 广度优先搜索 数组 1+	🟠	🀄️ 🔗
530	二叉搜索树的最小绝对差	[✓]	树 深度优先搜索 广度优先搜索 2+	🟢	🀄️ 🔗
536	从字符串生成二叉树 🔒		栈 树 深度优先搜索 2+	🟠	🀄️ 🔗
538	把二叉搜索树转换为累加树		树 深度优先搜索 二叉搜索树 1+	🟠	🀄️ 🔗
543	二叉树的直径	[✓]	树 深度优先搜索 二叉树	🟢	🀄️ 🔗
545	二叉树的边界 🔒		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
547	省份数量	[✓]	深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
549	二叉树最长连续序列 II 🔒		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
559	N 叉树的最大深度	[✓]	树 深度优先搜索 广度优先搜索	🟢	🀄️ 🔗
563	二叉树的坡度	[✓]	树 深度优先搜索 二叉树	🟢	🀄️ 🔗
565	数组嵌套		深度优先搜索 数组	🟠	🀄️ 🔗
572	另一棵树的子树	[✓]	树 深度优先搜索 二叉树 2+	🟢	🀄️ 🔗
582	杀掉进程 🔒		树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗
589	N 叉树的前序遍历	[✓]	栈 树 深度优先搜索	🟢	🀄️ 🔗
590	N 叉树的后序遍历	[✓]	栈 树 深度优先搜索	🟢	🀄️ 🔗
606	根据二叉树创建字符串		树 深度优先搜索 字符串 1+	🟠	🀄️ 🔗
617	合并二叉树	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
623	在二叉树中增加一行		树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
637	二叉树的层平均值	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
642	设计搜索自动补全系统 🔒		深度优先搜索 设计 字典树 4+	🔴	🀄️ 🔗
652	寻找重复的子树		树 深度优先搜索 哈希表 1+	🟠	🀄️ 🔗
653	两数之和 IV - 输入二叉搜索树	[✓]	树 深度优先搜索 广度优先搜索 4+	🟢	🀄️ 🔗
655	输出二叉树		树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
662	二叉树最大宽度	[✓]	树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
663	均匀树划分 🔒		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
666	路径总和 IV 🔒		树 深度优先搜索 数组 2+	🟠	🀄️ 🔗
669	修剪二叉搜索树		树 深度优先搜索 二叉搜索树 1+	🟠	🀄️ 🔗
671	二叉树中第二小的节点	[✓]	树 深度优先搜索 二叉树	🟢	🀄️ 🔗
672	灯泡开关 Ⅱ		位运算 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
676	实现一个魔法字典		深度优先搜索 设计 字典树 2+	🟠	🀄️ 🔗
684	冗余连接	[✓]	深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
685	冗余连接 II		深度优先搜索 广度优先搜索 并查集 1+	🔴	🀄️ 🔗
687	最长同值路径		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
690	员工的重要性		树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗
694	不同岛屿的数量 🔒		深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
695	岛屿的最大面积	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
711	不同岛屿的数量 II 🔒		深度优先搜索 广度优先搜索 并查集 2+	🔴	🀄️ 🔗
721	账户合并		深度优先搜索 广度优先搜索 并查集 4+	🟠	🀄️ 🔗
733	图像渲染	[✓]	深度优先搜索 广度优先搜索 数组 1+	🟢	🀄️ 🔗
737	句子相似性 II 🔒		深度优先搜索 广度优先搜索 并查集 3+	🟠	🀄️ 🔗
742	二叉树最近的叶节点 🔒		树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
743	网络延迟时间		深度优先搜索 广度优先搜索 图 2+	🟠	🀄️ 🔗
749	隔离病毒		深度优先搜索 广度优先搜索 数组 2+	🔴	🀄️ 🔗
753	破解保险箱		深度优先搜索 图 欧拉回路	🔴	🀄️ 🔗
756	金字塔转换矩阵		位运算 深度优先搜索 广度优先搜索	🟠	🀄️ 🔗
765	情侣牵手		贪心 深度优先搜索 广度优先搜索 2+	🔴	🀄️ 🔗
778	水位上升的泳池中游泳		深度优先搜索 广度优先搜索 并查集 4+	🔴	🀄️ 🔗
783	二叉搜索树节点最小距离	[✓]	树 深度优先搜索 广度优先搜索 2+	🟢	🀄️ 🔗
785	判断二分图		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
787	K 站中转内最便宜的航班		深度优先搜索 广度优先搜索 图 3+	🟠	🀄️ 🔗
797	所有可能的路径		深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
802	找到最终的安全状态	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
814	二叉树剪枝		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
827	最大人工岛	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🔴	🀄️ 🔗
834	树中距离之和		树 深度优先搜索 图 1+	🔴	🀄️ 🔗
839	相似字符串组		深度优先搜索 广度优先搜索 并查集 3+	🔴	🀄️ 🔗
841	钥匙和房间	[✓]	深度优先搜索 广度优先搜索 图	🟠	🀄️ 🔗
851	喧闹和富有		深度优先搜索 图 拓扑排序 1+	🟠	🀄️ 🔗
863	二叉树中所有距离为 K 的结点		树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗
865	具有所有最深节点的最小子树		树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗
872	叶子相似的树	[✓]	树 深度优先搜索 二叉树	🟢	🀄️ 🔗
886	可能的二分法		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
897	递增顺序搜索树	[✓]	栈 树 深度优先搜索 2+	🟢	🀄️ 🔗
924	尽量减少恶意软件的传播		深度优先搜索 广度优先搜索 并查集 3+	🔴	🀄️ 🔗
928	尽量减少恶意软件的传播 II		深度优先搜索 广度优先搜索 并查集 3+	🔴	🀄️ 🔗
934	最短的桥		深度优先搜索 广度优先搜索 数组 1+	🟠	🀄️ 🔗
938	二叉搜索树的范围和	[✓]	树 深度优先搜索 二叉搜索树 1+	🟢	🀄️ 🔗
947	移除最多的同行或同列石头		深度优先搜索 并查集 图 1+	🟠	🀄️ 🔗
951	翻转等价二叉树	[✓]	树 深度优先搜索 二叉树	🟠	🀄️ 🔗
959	由斜杠划分区域		深度优先搜索 广度优先搜索 并查集 3+	🟠	🀄️ 🔗
965	单值二叉树	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
968	监控二叉树		树 深度优先搜索 动态规划 1+	🔴	🀄️ 🔗
971	翻转二叉树以匹配先序遍历		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
979	在二叉树中分配硬币		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
987	二叉树的垂序遍历		树 深度优先搜索 广度优先搜索 3+	🔴	🀄️ 🔗
988	从叶结点开始的最小字符串		树 深度优先搜索 字符串 2+	🟠	🀄️ 🔗
993	二叉树的堂兄弟节点	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
1020	飞地的数量		深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
1022	从根到叶的二进制数之和	[✓]	树 深度优先搜索 二叉树	🟢	🀄️ 🔗
1026	节点与其祖先之间的最大差值		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
1028	从先序遍历还原二叉树	[✓]	树 深度优先搜索 字符串 1+	🔴	🀄️ 🔗
1034	边界着色		深度优先搜索 广度优先搜索 数组 1+	🟠	🀄️ 🔗
1036	逃离大迷宫		深度优先搜索 广度优先搜索 数组 1+	🔴	🀄️ 🔗
1038	从二叉搜索树到更大和树		树 深度优先搜索 二叉搜索树 1+	🟠	🀄️ 🔗
1042	不邻接植花		深度优先搜索 广度优先搜索 图	🟠	🀄️ 🔗
1080	根到叶路径上的不足节点		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
1102	得分最高的路径 🔒		深度优先搜索 广度优先搜索 并查集 4+	🟠	🀄️ 🔗
1110	删点成林		树 深度优先搜索 数组 2+	🟠	🀄️ 🔗
1120	子树的最大平均值 🔒		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
1123	最深叶节点的最近公共祖先		树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗
1145	二叉树着色游戏		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
1161	最大层内元素和	[✓]	树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
1192	查找集群内的关键连接		深度优先搜索 图 双连通分量	🔴	🀄️ 🔗
1202	交换字符串中的元素		深度优先搜索 广度优先搜索 并查集 4+	🟠	🀄️ 🔗
1203	项目管理		深度优先搜索 广度优先搜索 图 1+	🔴	🀄️ 🔗
1214	查找两棵二叉搜索树之和 🔒		栈 树 深度优先搜索 4+	🟠	🀄️ 🔗
1233	删除子文件夹	[✓]	深度优先搜索 字典树 数组 1+	🟠	🀄️ 🔗
1236	网络爬虫 🔒		深度优先搜索 广度优先搜索 字符串 1+	🟠	🀄️ 🔗
1242	多线程网页爬虫 🔒		深度优先搜索 广度优先搜索 多线程	🟠	🀄️ 🔗
1245	树的直径 🔒		树 深度优先搜索 广度优先搜索 2+	🟠	🀄️ 🔗
1254	统计封闭岛屿的数目		深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
1257	最小公共区域 🔒		树 深度优先搜索 广度优先搜索 3+	🟠	🀄️ 🔗
1261	在受污染的二叉树中查找元素	[✓]	树 深度优先搜索 广度优先搜索 3+	🟠	🀄️ 🔗
1267	统计参与通信的服务器	[✓]	深度优先搜索 广度优先搜索 并查集 3+	🟠	🀄️ 🔗
1273	删除树节点 🔒		树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
1302	层数最深叶子节点的和		树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
1305	两棵二叉搜索树中的所有元素		树 深度优先搜索 二叉搜索树 2+	🟠	🀄️ 🔗
1306	跳跃游戏 III		深度优先搜索 广度优先搜索 数组	🟠	🀄️ 🔗
1315	祖父节点值为偶数的节点和		树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
1319	连通网络的操作次数		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
1325	删除给定值的叶子节点		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
1339	分裂二叉树的最大乘积		树 深度优先搜索 二叉树	🟠	🀄️ 🔗
1361	验证二叉树		树 深度优先搜索 广度优先搜索 3+	🟠	🀄️ 🔗
1367	二叉树中的链表		树 深度优先搜索 链表 1+	🟠	🀄️ 🔗
1372	二叉树中的最长交错路径	[✓]	树 深度优先搜索 动态规划 1+	🟠	🀄️ 🔗
1373	二叉搜索子树的最大键值和		树 深度优先搜索 二叉搜索树 2+	🔴	🀄️ 🔗
1376	通知所有员工所需的时间		树 深度优先搜索 广度优先搜索	🟠	🀄️ 🔗
1377	T 秒后青蛙的位置		树 深度优先搜索 广度优先搜索 1+	🔴	🀄️ 🔗
1379	找出克隆二叉树中的相同节点	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
1382	将二叉搜索树变平衡		贪心 树 深度优先搜索 3+	🟠	🀄️ 🔗
1391	检查网格中是否存在有效路径		深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
1430	判断给定的序列是否是二叉树从根到叶的路径 🔒		树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
1443	收集树上所有苹果的最少时间		树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
1448	统计二叉树中好节点的数目	[✓]	树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
1457	二叉树中的伪回文路径		位运算 树 深度优先搜索 2+	🟠	🀄️ 🔗
1462	课程表 IV	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗