每日一题

July 29, 2021

1104. 二叉树寻路

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

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