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

101. 对称二叉树

题目描述 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 说明: 如果你可以运用递归和迭代两种方法解决这个问题,会很加分。 https://leetcode-cn.com/problems/symmetric-tree/ 解法1 为了解决问题,我们先画一个比较general的case来帮助我们思考。我们构建一个4层的对称二叉树,如图1所示。我们可以发现,如果一颗树是对称二叉树,那么它的左子树与右子树是互为镜像的。如图1所示,跟节点root的左子树root.left与右子树root.right互为镜像。因此,我们可以把问题转化为判断两个二叉树是否互为镜像。 为了判断两颗二叉树是否互为镜像,我们创建函数private boolean isMirror(TreeNode node1, TreeNode node2),用来判定两颗二叉树node1与node2是否互为镜像。那我们如何实现这个函数呢? 首先,如果node1与node2都是空,很好理解,他们是镜像的。 如果node1与node2有一个为空,另一个非空,那么肯定不是镜像的。 如果node1与node2都非空,但是node对应的值不想相等,那么也不互为镜像。 如果node1与node2非空,且值相等,那我们还需要递归的判断node1的右子树与node2的左子树互为镜像,且node1的左子树与node2的右子树互为镜像。 我们按照上面的规则递归的判定,直到我们都访问到叶节点后返回我们才能确定两棵树是互为镜像的。如果在递归的过程中发现有不符合上述规则都情况,那么这两棵树就不是镜像的。 下面的代码采用DFS方式判定,我们按照上面4条规则实现了isMirror函数,然后我们把root的左子树与右子树传递给isMirror函数就能够判定整棵树是否是对称的。 解法2 解法2采用另一个比较直观的思路,比较容易理解。我们观察图1,如果树是对称的,那么我们横向读取每一层的节点,都会发现他们是“回文序列”,也就是从左到右读和从右到左读都是一样的。如果有任何一层读起来不是回文序列,那么这棵树就不是对称的! 为了实现按层次遍历,我们使用BFS算法,用一个队列来实现。但是队列没法随机访问,我们在实现时使用数组来模拟队列。如果使用数组的remove方法来出队,会涉及到元素移动,使得时间复杂度达到O(n^2)。因此,我们采用“双缓冲”方法,创建变量queue以及buffer,从queue中读取当前层到节点并访问,将下一层节点放入buffer,然后交换queue与buffer。如果你不清楚二叉树层次变量,可以参考这个。 时间复杂度为O(n),空间复杂度为O(n)。全部代码如下:

Read more

100. 相同的树

题目描述 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true 示例 2: 输入: 1 1 / \ 2 2 [1,2], [1,null,2] 输出: false 示例 3: 输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] 输出: false https://leetcode-cn.com/problems/same-tree/ 解法1 两棵树相同的定义是结构上相同,且对应位置的值相同。我们首先考虑两颗二叉树,每个二叉树是由3个节点构成的满二叉树。先对比跟节点,如果跟节点的值不相同那么就不用继续比了。如果跟节点的值相同,再分别对比两棵树的左右叶子结点。将上面的过程一般化,如果树由多层的节点构成,我们需要递归的对比左右子树。如果节点缺失了左/右子树,那么另一颗树的相应位置也应该为null。 我们按照上面的说明编写代码,时间复杂度为O(n),空间复杂度为O(n)(树为“线性的“情况下,调用栈的开销),n为节点数量。全部代码如下:

Read more

102. 二叉树的层次遍历

题目描述 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 解法1 – BFS 解法1不用多说,在课本中,考研题中经常出现。我们使用队列,将跟节点加入队列,然后出队并访问,再将出队节点的左右子树再一次加入队列……直到队列为空。这种解法很自然,也很容易想到。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – DFS 这道题也可以采用DFS解法,层次其实就是深度,我们记录遍历到每一层级到深度,为每一层级创建List,根据当前深度找到对应的List,然后追加进去。在实现的时候,我们采用先序遍历的,如果采用中序/后序遍历,下面的代码需要略微调整,将if改为while。因为先序遍历能够保证为深度比当前节点浅的所有节点都创建相应的List。而中序/后序遍历会先走到最深的左/右子树,我们必须使用循环为所有层级比当前浅的节点创建对应的List。 DFS理论上会比BFS慢一些,因为存在函数调用与调用栈创建等开销。此外,如果树的层级过高,会有“爆栈”的风险。时间复杂度O(n),空间复杂度O(n)。全部代码如下:

Read more

Leetcode 144/94/145 – 二叉树的前序/中序/后续遍历

题目1描述 给定一个二叉树,返回它的 前序 遍历。  示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3] 进阶: 递归算法很简单,你可以通过迭代算法完成吗? https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ 解法1 – 递归算法 递归解法:定义一个函数private void preorder(TreeNode node, List ans),如果node为空则返回,否则将node.val添加到ans中。然后依次递归调用preorder(node.left, ans)访问node的左子树;递归调用preorder(node.right, ans)访问node的右子树。 时间复杂度O(n),空间复杂度O(n)(递归过程中会创建调用栈,实际上还是有额外空间的),其中n为二叉树节点数量。全部代码如下: 解法2 – 迭代算法 我们创建栈stack,首先将跟节点入栈,然后取出栈顶元素node访问,将node.val加入到结果数组ans中。然后,我们将右子树、左子树依次入栈(如果他们不为空)。因为先序遍历需要依次访问跟节点、左子树、右子树,所以我们需要先将右子树入栈,再将左子树入栈。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 题目2描述 给定一个二叉树,返回它的中序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2] 进阶: 递归算法很简单,你可以通过迭代算法完成吗? https://leetcode-cn.com/problems/binary-tree-inorder-traversal/ 解法1 – 递归算法 和题目1的递归算法类似,我们只需要调整访问node的顺序,使其先递归访问node的左子树;然后将node.val加入到结果数组;最后递归访问node的右子树即可。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 解法2 – 迭代算法 为了能够将递归算法转化为迭代算法,我们需要模拟调用栈的过程。中序遍历要求最先访问左子树,那我们就创建栈stack,变量node指向当前节点,一直向左下角走,将沿途的节点都加入到stack中,直到走到空节点。当走到空节点时,我们从栈中弹出一个节点并访问,这就是第一个被访问的左子节点。然后我们将node指向node的右子树(node =…

Read more

324. 摆动排序 II

题目描述 给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。 示例 1: 输入: nums = [1, 5, 1, 1, 6, 4] 输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6] 示例 2: 输入: nums = [1, 3, 2, 2, 3, 1] 输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2] 说明:你可以假设所有输入都会得到有效的结果。 进阶:你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗? https://leetcode-cn.com/problems/wiggle-sort-ii/ 解法1 –…

Read more

215. 数组中的第K个最大元素

题目描述 在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明: 你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ 解法1 – 排序O(nlogn) 这是一道经典的题目,有多种解法。最直接的想法,我们可以先排序,然后取出第n – k个数字。时间复杂度O(nlogn),空间复杂度O(1)。全部代码如下: 运行时间:7ms 解法2 – 堆(优先队列)O(nlogk) 我们维护一个大小为k的最小堆,这可以通过Java的PriorityQueue的默认构造方法构建。我们不断的往堆中加入元素,直到元素数量超过k,我们删除最小元素。当扫描完整个nums数组,堆中就留下了k个最大的数,我们取k个最大数中最小的那一个就是答案。 例如nums = {3,2,1,5,6,4}, k = 2。当堆内容为{3, 2}时,再加入1得到{3, 2, 1},元素数量超过了k,我们删除最小元素1得到{3,…

Read more

376. 摆动序列

题目描述 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。 给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。 示例 1: 输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。 示例 2: 输入: [1,17,5,10,13,15,10,5,16,8] 输出: 7 解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。 示例 3: 输入: [1,2,3,4,5,6,7,8,9] 输出: 2 进阶:你能否用 O(n) 时间复杂度完成此题? https://leetcode-cn.com/problems/wiggle-subsequence/ 解法1 – 动态规划 O(n^2) 我们定义dp数组为dp[|nums|][2],dp[i][0]表示第i个元素作为较小元素构成的摆动序列最大长度;dp[i][1]表示第i个元素作为较大元素构成的摆动序列最大长度,且必须使用nums[i]。那么我们有dp[i][0] = dp[j][1]+1如果存在nums[j] > nums[i],否则dp[i][0]=1;dp[i][1] = dp[j][0]+1如果存在nums[j] < nums[i],否则dp[i][1]=1(0<=j<i)。 需要注意,当我们填充dp[i][0/1]时,我们向前寻找dp[j][1/0],不能找到第一个大于/小于nums[i]的元素后就停止,而是应该搜索到j = 0。因为有这样的case: 例如图1中的case,当i=4时nums[4]=0,当我们更新dp[4][0]时,我们不能只向前搜寻第一个大于nums[4]的位置。因为前面可能有更长的摆动序列,能够和0链接上,形成更长的摆动序列。在这个例子中,{53,1,3,1}与{1}都能和[0]形成摆动序列,但是我们要选最长的。 该方法的时间复杂度为O(n^2),空间复杂度为O(n)。全部代码如下: 解法2 – 动态规划 O(n) 我们还是使用动态规划,但是我们更改了dp数组的定义。我们定义数组dp[|nums|][2],dp[i][0]表示nums前i个数构成的摆动序列最大长度且序列最后一个数是较小的;dp[i][1]表示nums前i个数构成的摆动序列最大长度且序列最后一个数是较大的。那么有dp[i][0]…

Read more