二叉树

July 30, 2021

1254. 统计封闭岛屿的数目

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

Read More
July 29, 2021

1104. 二叉树寻路

1104. 二叉树寻路 思路: 本题有两种解法,第一种是模拟第二种是用数学的方法,首先要考虑的是若一个二叉树没有奇偶性质,那么他的父节点一定是 当前节点/2;因此,在得知某一层的最大值和最小值后,我们便可以由计算或模拟来得到其父节点: 利用从根节点到任意一层都是满二叉树,我们可以先确定 label 所在的层级 level,然后计算出当前层起始节点值(最小值)和结束节点值(最大值)。再利用「每层节点数量翻倍」&「隔层奇偶性翻转」,寻址出上一层的节点下标(令每层下标均「从左往右」计算,并从 11 开始),直到构造出答案(寻址到根节点)。...

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
July 25, 2021

173. 二叉搜索树迭代器

173. 二叉搜索树迭代器 两种做法: 中序递归遍历:我们可以直接对二叉搜索树做一次完全的递归遍历,获取中序遍历的全部结果并保存在数组中。随后,我们利用得到的数组本身来实现迭代器。 /** * Definition for a binary tree...

Read More