- 博客(103)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 Leetcode 222. 完全二叉树的节点个数
题目解答解法一：全部遍历代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class S...
2019-07-30 23:51:10
798
原创 Leetcode 199. 二叉树的右视图
题目给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例:来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-right-side-view著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解答解法一：递归 + dfs深搜，优先搜索右子树。只将同一...
2019-07-29 23:24:32
388
原创 Leetcode 173. 二叉搜索树迭代器
题目实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用 next() 将返回二叉搜索树中的下一个最小的数。BSTIterator iterator = new BSTIterator(root);iterator.next(); // 返回 3iterator.next(); // 返回 7iterator.hasNext(); // 返回 true...
2019-07-29 23:01:06
239
原创 Leetcode 145. 二叉树的后序遍历
题目给定一个二叉树，返回它的 后序 遍历。进阶: 递归算法很简单，你可以通过迭代算法完成吗？来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解答解法一：递归递归解法不用多说，很简单。代码/**...
2019-07-29 17:17:49
269
原创 Leetcode 144. 二叉树的前序遍历
题目给定一个二叉树，返回它的 前序 遍历。进阶: 递归算法很简单，你可以通过迭代算法完成吗？来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解答解法一：递归递归算法不用多说，很简单。代码/** ...
2019-07-28 23:10:04
124
原创 Leetcode 129. 求根到叶子节点数字之和
题目给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶子节点生成的所有数字之和。说明: 叶子节点是指没有子节点的节点。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sum-root-to-leaf-...
2019-07-28 19:50:49
462
原创 Leetcode 124. 二叉树中的最大路径和
题目给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解答递...
2019-07-27 22:10:06
446
原创 Leetcode 117. 填充每个节点的下一个右侧节点指针 II
题目给定一个二叉树struct Node {int val;Node *left;Node *right;Node *next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。提示：你只能使用常量级额外空间。使用递归解题也符合要求，本题中...
2019-07-27 20:57:01
380
原创 Leetcode 116. 填充每个节点的下一个右侧节点指针
题目给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：struct Node {int val;Node *left;Node *right;Node *next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL...
2019-07-27 15:10:21
180
原创 Leetcode 114. 二叉树展开为链表
题目来自力扣：leetcode 解答解法一：代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * }...
2019-07-27 14:08:46
434
原创 Leetcode 113. 路径总和 II
题目给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。来自力扣：leetcode 113. 路径总和 II解答本题是 Leetcode 112. 路径总和 的变种题，只需要将走过的路径保存下来即可。最简单的方法是 递归解法 。递归步骤如下：使用一个 cur 列表保存已经走过的路径，遍历完左右子树后再回退。...
2019-07-26 21:47:27
260
原创 Leetcode 112. 路径总和
题目给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。来自力扣：leetcode 112. 路径总和解答解法一：递归按照前序遍历的顺序递归。当到达叶子结点的时候，判断此时 sum 是否能被减成 0。代码/** * Definition for a binary tree node....
2019-07-26 21:29:02
163
原创 Leetcode 111. 二叉树的最小深度
题目给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。解答解法一：递归具体如下：如果当前结点为空，返回 0如果左子树是空，返回右子树的最小深度 + 1如果右子树是空，返回左子树的最小深度 + 1如果左子树和右子树都不为空，返回二者最小的深度 + 1代码/** * Definition for...
2019-07-26 20:27:42
129
原创 Leetcode 110. 平衡二叉树
题目给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。解答解法一：多次遍历 O(n^2)思路简单。对于每一个结点都需要遍历一下左右子树，找到左右子树高度，然后判断是否符合平衡二叉树条件。这导致时间复杂度变成 O(n^2) 。代码/** * Definition for a bin...
2019-07-26 14:47:36
246
原创 Leetcode 108. 将有序数组转换为二叉搜索树
题目将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。解答解法一：递归递归比较好理解。步骤如下：取区间的中点作为根节点。构造左子树 。构造右子树。代码/** * Definition for a binary tree node. * public class Tr...
2019-07-26 13:39:01
148
原创 Leetcode 107. 二叉树的层次遍历 II
题目给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）解答解法一：递归其实本题还是 Leetcode 102. 二叉树的层次遍历 的一个变种题。对于二叉树层序遍历的结果反向一下就好了。。二叉树的层次遍历：点这里代码/** * Definition for a binary tree node. * public cla...
2019-07-25 22:48:43
411
原创 Leetcode 104. 二叉树的最大深度
题目给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。解答本题可以使用多种方式：先序，中序，后序，层序等等的都行。不论怎么实现遍历：递归，栈，Mirros 均可。对于这些方式就不再多说了。最简单的方式还是递归。可以看出：null 的深度是 0。每个结点的最大深度 = max(左子树的最大深度...
2019-07-25 19:33:44
151
原创 Leetcode 103. 二叉树的锯齿形层次遍历
题目解答解法一：递归前一道题目 Leetcode 102. 二叉树的层次遍历 的变种题。递归方式只需要在原来的基础上增加一个奇偶层判断即可。二叉树的层次遍历 博客地址：二叉树的层次遍历代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNod...
2019-07-25 19:19:49
173
原创 Leetcode 102. 二叉树的层次遍历
题目给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。解答解法一：递归深度等价于层级， 可利用深度来判断当前结点所处的层级。进而可以根据当前结点的深度定位其在 res 的下标位置。代码/** * Definition for a binary tree node. * public class TreeNode { * int val;...
2019-07-25 18:41:52
190
原创 Leetcode 101. 对称二叉树
题目给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。说明:如果你可以运用递归和迭代两种方法解决这个问题，会很加分。解答解法一：递归本题是 Leetcode 100. 相同的树 的变种题。Leetcode 100. 相同的树 可看我上篇博客：上篇博客。本题递归思路：如果当前值不相等，结束。否则因为为镜像树，所以需要递归 (...
2019-07-25 18:06:52
200
原创 Leetcode 100. 相同的树
题目给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。解答解法一：队列 + 迭代使用队列，将两棵树相同位置的结点放在一个 Couple 中。如果 Couple 比对不相等，直接返回 false。否则如果当前结点不为 null，就把新的左右结点加入队列。代码/** * Definition for a binary...
2019-07-25 17:44:48
162
原创 Leetcode 99. 恢复二叉搜索树
题目二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？解答本题需要找到两个需要交换的结点使得二叉搜索树结构恢复。思路：如若按照中序遍历的序列来讲，问题就转化为找中序遍历结果的两个逆序对。中序遍历算法的复杂度如下：递归：O(n) 时间，O(n) 空间。栈：O...
2019-07-25 14:46:30
315
原创 Leetcode 98. 验证二叉搜索树
题目给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。解答解法一：中序遍历结果有序利用二叉搜索树的中序遍历结果有序的特性。复杂度：O(n) 时间， O(n) 空间。代码/** * Definition for a binar...
2019-07-25 13:36:37
119
原创 Leetcode 96. 不同的二叉搜索树
题目解答解法一：递归代码class Solution { public int numTrees(int n) { return numTrees(1, n); } private int numTrees(int start, int end) { if(start > end) { ret...
2019-07-25 12:50:58
282
2
原创 Leetcode 95. 不同的二叉搜索树 II
题目解答：递归我们知道二叉搜索树的特点：左子树 < 自己 < 右子树所以如果想找到 1…n 所有的二叉搜索树序列，只需要找以 1…n 中的每一个数作为根节点的左右子树能组成的所有可能即可。例如：1 … 3 之间的所有二叉搜索树的可能的组成是：以 1 为根节点：左子树为 null，右子树为 2 … 3 组成的全部可能的子树。以 2 为根节点：左子树为 1 形成的子树，右子...
2019-07-25 00:24:33
285
原创 Leetcode 94. 二叉树的中序遍历
题目给定一个二叉树，返回它的中序 遍历。示例:输入: [1,null,2,3]输出: [1,3,2]进阶:递归算法很简单，你可以通过迭代算法完成吗？解答解法一：递归递归遍历没什么难度，这里不细说了。复杂度：O(n) 时间，O(n) 空间。代码/** * Definition for a binary tree node. * public class Tree...
2019-07-24 23:24:38
180
原创 Leetcode 227. 基本计算器 II
题目实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。示例 1:输入: “3+2*2”输出: 7示例 2:输入: " 3/2 "输出: 1示例 3:输入: " 3+5 / 2 "输出: 5说明：你可以假设所给定的表达式都是有效的。请不要使用内置的库函数 ev...
2019-07-24 20:22:27
138
原创 Leetcode 165. 比较版本号
题目比较两个版本号 version1 和 version2。如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。你可以假设版本字符串非空，并且只包含数字和 . 字符。. 字符不代表小数点，而是用于分隔数字序列。例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。你可...
2019-07-24 15:38:44
136
原创 Leetcode 151. 翻转字符串里的单词
题目给定一个字符串，逐个翻转字符串中的每个单词。示例 1：输入: “the sky is blue”输出: “blue is sky the”示例 2：输入: " hello world! "输出: “world! hello”解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。示例 3：输入: “a good example”输出...
2019-07-24 14:27:05
111
原创 Leetcode 125. 验证回文串
题目给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。示例 1:输入: “A man, a plan, a canal: Panama”输出: true示例 2:输入: “race a car”输出: false本题解答：双指针本题双指针解法介绍：一个从头开始一直找到字母/数字停止。一个...
2019-07-23 22:48:35
102
原创 Leetcode 115. 不同的子序列
题目给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）示例 1:输入: S = “rabbbit”, T = “rabbit”输出: 3解释:如下图所示, 有 3 种可以从 S ...
2019-07-23 21:53:05
266
原创 Leetcode 72. 编辑距离
题目给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例 1:输入: word1 = “horse”, word2 = “ros”输出: 3解释:horse -> rorse (将 ‘h’ 替换为 ‘r’)rorse -> rose...
2019-07-23 00:00:23
181
原创 Leetcode 97. 交错字符串
题目给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例 1:输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”输出: true示例 2:输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”输出: false解答解法一：递归代码很容易理...
2019-07-22 23:56:33
223
原创 Leetcode 93. 复原IP地址
题目给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。示例:输入: “25525511135”输出: [“255.255.11.135”, “255.255.111.35”]解答使用 回溯法 每次都拆分出一个合法的地址段，递归到底 (n == 4) 时判断整个地址是否合法即可。具体如下：每次递归都会截取一段 (1 - 3个字符) 的字符串。判断地址段是否合...
2019-07-22 22:50:53
188
原创 Leetcode 91. 解码方法
题目一条包含字母 A-Z 的消息通过以下方式进行了编码：‘A’ -> 1‘B’ -> 2…‘Z’ -> 26给定一个只包含数字的非空字符串，请计算解码方法的总数。示例 1:输入: “12”输出: 2解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。示例 2:输入: “226”输出: 3解释: 它可以解码为 “BZ” (2 26), “...
2019-07-22 22:08:52
109
原创 Leetcode 76. 最小覆盖子串
题目给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。示例：输入: S = “ADOBECODEBANC”, T = “ABC”输出: “BANC”说明：如果 S 中不存这样的子串，则返回空字符串 “”。如果 S 中存在这样的子串，我们保证它是唯一的答案。解答使用滑动窗口算法思想。滑动窗口问题通用模板如下（本文章的重点内容！）...
2019-07-22 16:14:06
281
原创 Leetcode 71. 简化路径
题目以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有...
2019-07-22 00:38:51
114
原创 Leetcode 67. 二进制求和
题目给定两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。示例 1:输入: a = “11”, b = “1”输出: “100”示例 2:输入: a = “1010”, b = “1011”输出: “10101”解答从最后一位开始运算，模拟一下进位就行了。代码很容易看懂，不多说啦。代码class Solution { ...
2019-07-21 23:24:45
92
原创 Leetcode 58. 最后一个单词的长度
题目给定一个仅包含大小写字母和空格 ’ ’ 的字符串，返回其最后一个单词的长度。如果不存在最后一个单词，请返回 0 。说明：一个单词是指由字母组成，但不包含任何空格的字符串。示例:输入: “Hello World”输出: 5解答很简单的一道题，注意倒着找就好了。具体如下：从后面倒着找到最后一个不是空格的位置 gt 。然后从这个位置开始，找到第一个为空格或者超界的位置 l...
2019-07-21 22:37:24
96
原创 Leetcode 49. 字母异位词分组
题目给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。示例:输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],输出:[[“ate”,“eat”,“tea”],[“nat”,“tan”],[“bat”]]说明：所有输入均为小写字母。不考虑答案输出的顺序。解答解法一：代码结果扩...
2019-07-21 22:16:52
638
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人