307. 区域和检索 – 数组可修改

题目描述 给定一个整数数组  nums,求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和,包含 i,  j 两点。 update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。 示例: Given nums = [1, 3, 5] sumRange(0, 2) -> 9update(1, 2)sumRange(0, 2) -> 8说明: 数组仅可以在 update 函数下进行修改。 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/range-sum-query-mutable著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Prefix sum 我们可以预先计算出前缀和存储在数组中,prefix[i] = num[0]+…+nums[i]。这样,当需要求得范围[i,j]的和时,我们可以通过prefix[j]-prefix[i-1]在O(1)的时间计算出结果。但是当nums[i]发生更新操作,那么我们不得不重新计算prefix[i]之后的前缀和,时间复杂度为O(n)。 全部代码如下: 解法2 – Fenwick Tree(树状数组) Fenwick Tree也称为树状数组,它可以在O(logn)的时间得到任意前缀和,并同时支持在O(logn)时间内支持动态单点值的修改。空间复杂度O(n)。为了实现Fenwick Tree,我们需要一个函数lowbit(x),他是用来求得数值x最低位第一个1所代表到数值,例如x = 0110,lowbit(x) = 0010; x = 0101, lowbit(x) = 0001。…

Read more

337. 打家劫舍 III

题目描述 在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。 计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。 示例 1: 输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 示例 2: 输入: [3,4,5,1,3,null,1]   3 / \ 4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9. 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/house-robber-iii著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1…

Read more

110. 平衡二叉树

题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 https://leetcode-cn.com/problems/balanced-binary-tree/ 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/balanced-binary-tree著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Top-down 我们就按照定义来,求得节点左右子树的高度(在实现时用的深度),如果相差不超过1,这个子树就是平衡二叉树。我们递归地对每一个节点都进行这样的判断,直到最后轮到判断跟节点。如果跟节点也满足这样的定义,那么这棵树就是平衡二叉树。 对于求得一个顶点的深度的算法,时间复杂度为O(n)。但是二叉树有n个节点,总体时间复杂度为O(n^2)。如果树是链式结构,那么空间复杂度最高,为O(n)。全部代码如下: 解法2 – Bottom-up Bottom-up算法自下而上地求得每个顶点的高度,根据左右子树的高度差判断是否平衡。如果某个顶点的左右子树的高度之差已经超过1了,那么我们也不必要继续向上判断了。这样,我们发现有任何一颗子树是不平衡的,我们就可以提前终止算法。就算了所有的子树都是平衡点,所有顶点也只扫描一次。 因此Bottom-up算法的时间复杂度O(n),空间复杂度O(n)。全部代码如下:

Read more

104. 二叉树的最大深度

题目描述 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – DFS 这是道经典的BinaryTree的模版题,我们声明函数private int helper(TreeNode node, int depth) ,当node是叶子结点时返回depth,如果node的左子树非空则递归调用helper(node.left, depth+1);当node的右子树非空,则递归调用helper(node.right, depth+1); 当node为空,则返回0。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – BFS 当然这道题也可以用BFS来做,我们需要一个队列,还有一个Map<TreeNode, Integer>用来存放节点对应的深度。如果node的左子树非空,就将它如队列,然后depth+1放入map中;右子树同理。然后还需要一个存放答案的变量ans,如果取出节点的深度大于ans就更新它,最后返回ans。 复杂度和解法1相同,但因为用到了Map导致overhead比较大,实际运行时间比解法1慢很多。全部代码如下:

Read more

111. 二叉树的最小深度

题目描述 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最小深度  2. 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – DFS 解法1简单的很,我们就用DFS遍历二叉树,声明一个辅助函数用来遍历private int helper(TreeNode node, int depth)。node是当前节点,depth是当前节点深度。如果当前节点是叶节点,就返回depth;如果node左子树非空,就递归遍历左子树求最小深度;如果node右子树非空,就递归遍历右子树求最小深度,然后取左右子树最小深度的min并返回。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – BFS 解法2用队列实现BFS,但是还需要用一个辅助的Map<TreeNode, Integer>记录节点与它的深度。首先从队列出队一个节点,然后从Map取出该节点深度currLevel。每当下一层的节点入队,就将被入队的节点作为key,currLevel+1作为value存入Map中。当发现出队的节点为叶节点时,就终止BFS过程,返回currLevel作为结果。 BFS遍历的好处是,如果首先碰到了叶节点就可以终止遍历过程。而DFS方式需要遍历所有节点才能够知道最小深度。但是最坏情况下BFS和DFS的时间复杂度是一样的,此外BFS还需要用Map存储节点与深度的对应关系,耗费额外的空间;而访问Map还会有一些开销,因此性能并没有DFS好。

Read more

129. 求根到叶子节点数字之和

题目描述 给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。 例如,从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此,数字总和 = 12 + 13 = 25. 示例 2: 输入: [4,9,0,5,1] 4 / \ 9 0  / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字…

Read more

113. 路径总和 II

题目描述 给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例:给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] https://leetcode-cn.com/problems/path-sum-ii/ 解法1 这道题是“112. 路径总和”的升级版本,在这道题我们需要把所有可能的解都存储下来并返回。为了记录路过的节点,我们使用一个变量List<Integer> path来存储路过的节点的值。我们将每个路过的节点的值都放入path中,如果走到叶节点发现是一条可行的路径(节点值之和等于sum),我们就复制path数组,然后放入到结果变量List<List<Integer>> ans。当从节点返回时,我们需要回溯以保证path变量的正确性。 上面的思路可以使用二叉树的先序遍历来实现。我们用题目给的case来描述执行过程:我们不断地向左走,找到一条路径”5->4->11->7″,path变量的内容依次变为[5], [5, 4], [5, 4, 11], [5, 4, 11, 7]。然后我们发现这条路径的和不等与sum,我们从节点7回溯,path变量从[5,4,11,7]变为[5,4,11],回到节点11走向它的右子树,此时path变量为[5,4,11,2],发现路径和与sum相等,复制path数组的到ans。因为我们需要复用path数组,所以不能直接调用ans.add(path),而是应该调用ans.add(new ArrayList<>(path)),创建path的副本并加入到ans中。 假设我们不考虑path数组复制的过程,那么时间复杂度为O(n)(因为要遍历所有节点),空间复杂度为O(n)(空间为调用栈开销)。

Read more

112. 路径总和

题目描述 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。 https://leetcode-cn.com/problems/path-sum/ 解法1 这道题采用DFS就可以实现,我们每路过一个节点,就把节点值从sum中减掉,然后传递给节点的左子树/右子树。当遍历到叶子节点时sum为0,就找到了这么一条路径。由于这条路径可能从当前节点“向左走”也可能“向右走”,他们应该取或的关系。 需要注意的是,有一个case: node = null, sum = 0,它的答案是false,也就是不存在一条路径使得和为0。我一开始写的代码是这样的: 如果这么写,对于上面的case会返回true。我们应该在当前节点为叶子结点时,判定sum是否为0,而不是遇到空节点时再判断,这样就能够使得那个case返回false。下面是正确的代码,时间复杂度和空间复杂度都为O(n):

Read more

257. 二叉树的所有路径

题目描述 给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 输入: 1 / \ 2 3 \ 5 输出: [“1->2->5”, “1->3”] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3 https://leetcode-cn.com/problems/binary-tree-paths/ 解法1 这道题目很简单,我们只需要先序遍历二叉树,把经过的节点都记录下来就可以了。唯一需要注意的是问题是,我们需要使用“->”连接路过的节点,当遇到叶节点时,我们不应该添加“->”。 我们要遍历全部节点,所以时间复杂度为O(n);当树为链表形态时,栈当深度最深,空间复杂度为O(n)。全部代码如下:

Read more

226. 翻转二叉树

题目描述 翻转一棵二叉树。 示例: 输入: 4 / \ 2 7 / \ / \ 1 3 6 9 输出: 4 / \ 7 2 / \ / \ 9 6 3 1 备注:这个问题是受到 Max Howell 的 原问题 启发的 : 谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。 https://leetcode-cn.com/problems/invert-binary-tree/ 解法1 这道题很简单,我们就把每一层节点的左子节点和右子节点交换,递归执行到叶节点即可。我们在图1绘制了节点交换的执行过程,首先我们交换跟节点4的左右子树,这里的交换不是指节点值的交换,而是引用的交换,这样才能让被交换节点的所有子树也都一同交换。接下来,我们递归交换节点7与2的左右子树。 时间复杂度为O(n),空间复杂度为O(n)。全部代码如下: 解法2 – 待续

Read more