深度优先搜索

July 30, 2021

1254. 统计封闭岛屿的数目

1254. 统计封闭岛屿的数目 此题是典型的岛屿问题;可以拆分为两个部分:寻找连通块已经去除边界的连通块; 此题中学到了用dx, dy来移动,并且用一个布尔数组来表示是否遍历过点来避免重复遍历;已经用flag传址来标记是否为边界上的连通块即不为封闭岛屿:代码如下: class Solution { // 记录x和y的移动值 public...

Read More
July 28, 2021

863. 二叉树中所有距离为 K 的结点

863. 二叉树中所有距离为 K 的结点 思路:DFS+哈希 第一次DFS来用哈希表存储节点和其父节点这样就可以在之后回溯得到距离为k的点 第二次DFS从target开始,以target为root,这样就可以用递归来找当前depth和k相同的节点了,需要注意的是,在回溯过程中会出现遍历过已经出现的数字的情况,因此我们需要记录下之前的节点是哪个。 ps:由于节点的值都不相同因此hashmap的key选择了值 代码: // /**...

Read More
July 27, 2021

671. 二叉树中第二小的节点

671. 二叉树中第二小的节点 此题有三种情况: 可以定义两个小值 d1, d2 若树上的值 X < d1 < d2 --> d1 = X d2 = d1; 若树上的值 d1 < X < d2 --> d2 = X; 若树上的值 d1 < d2 < X --> 不变// DFS: /** * Definition for...

Read More