斌同学斌同學-CSDN博客

原创（链表）2. 两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807题解思路将当前结点初始化为返回列表的哑结点。将进位carry 初始

2020-09-09 19:56:25 149

原创（二叉树）538. 把二叉搜索树转换为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。题解思路二叉搜索树的中序遍历的反序是一个降序数组，因此只需用一个sum记录到当前节点为止的所有数组和，并把这个值更新到二叉树的root节点即可，这样每个节点存的值就是原来节点值加上所有大于它节点的值之和实现代码class Solution { int sum = 0; public TreeNode convertBS

2020-09-09 19:15:17 133

原创（二叉树）617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。注意: 合并必须从两个树的根节点开始。题解思路在遍历时，如果两棵树的当前节点均不为空，我们就将它们的值进行相加，并对它们的左孩子和右孩子进行递归合并；如果其中有一棵树为空，那么我们返回另一颗树作为结果；如果两棵树均为空，此时返回任意一棵树均可（因为都是空）实

2020-09-08 12:08:19 142

原创（链表）82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。示例 1:输入: 1->2->3->3->4->4->5输出: 1->2->5示例 2:输入: 1->1->1->2->3输出: 2->3题解思路为了防止删除头结点的极端情况发生，先创建空结点dummy，使dummy指向传入的head结点。然后创建cur的指针，指向链表的头部（即dummy）。接着对cur指针迭代，因为要对比c

2020-09-08 10:24:02 125

原创（链表）83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。示例 1:输入: 1->1->2输出: 1->2示例 2:输入: 1->1->2->3->3输出: 1->2->3题解思路指定 cur 指针指向头部 head当 cur 和 cur.next 的存在为循环结束条件，当二者有一个不存在时说明链表没有去重复的必要了当 cur.val 和 cur.next.val 相等时说明需要去重，则将 cur 的下一个指针指向下一个的下一个，

2020-09-08 09:11:42 91

原创（数组）59. 螺旋矩阵 II

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。示例:输入: 3输出:[[ 1, 2, 3 ],[ 8, 9, 4 ],[ 7, 6, 5 ]]题解思路实现代码public class Solution02 { public int[][] generateMatrix(int n) { int[][] matrix = new int[n][n]; int left = 0, right =

2020-09-07 15:41:35 95

原创（数组）54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。示例 1:输入:[[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]输出: [1,2,3,6,9,8,7,4,5]示例 2:输入:[[1, 2, 3, 4],[5, 6, 7, 8],[9,10,11,12]]输出: [1,2,3,4,8,12,11,10,9,5,6,7]题解思路实现代码public class Solution {

2020-09-07 15:21:46 82

原创（二叉树）剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。示例 1：输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]题解思路终止条件：当节点 root为空时（即越过叶节点），则返回 null ；递推工作：初始化节点 tmp ，用于暂存 root 的左子节点；开启递归右子节点 mirrorTree(root.right) ，并将返回值作为 root 的左子节点。开启递归左子节点 mirrorTree(tmp) ，并将返回值作为 root 的右子节

2020-09-05 23:07:41 78

原创（二叉树）226. 翻转二叉树

翻转一棵二叉树。题解思路其实就是交换一下左右节点，然后再递归的交换左节点，右节点根据动画图我们可以总结出递归的两个条件如下：终止条件：当前节点为null时返回交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点实现代码class Solution { public TreeNode invertTree(TreeNode root) { //递归函数的终止条件，节点为空时返回 if(root==null) { return null; } /

2020-09-05 22:59:32 84

原创（二叉树）剑指 Offer 28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:示例 1：输入：root = [1,2,2,3,4,4,3]输出：true示例 2：输入：root = [1,2,2,null,3,null,3]输出：false题解思路如果两颗树的根都为空，返回true如果一颗为空另一颗不为空返回false如果两颗都不为空

2020-09-05 22:52:44 76

原创（链表）12. 相交链表

输入两个链表，找出它们的第一个公共节点。题解思路指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历如果 pA 到了末尾，则 pA = headB 继续遍历如果 pB 到了末尾，则 pB = headA 继续遍历比较长的链表指针指向较短链表head时，长度差就消除了如此，只需要将最短链表遍历两次即可找到位置实现代码public class Solution { public ListNode getIntersectionNode(ListNode headA, Li

2020-09-05 22:43:56 82

原创（链表）11. 单链表反转

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL题解思路双指针实现实现代码class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = hea

2020-09-05 22:39:48 83

原创（链表）3. 有序链表合并

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4题解思路终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束返回值：每一层调用都返回排序好的链表头本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理O(m+n)，m 为 l1的长度，n 为

2020-09-05 22:35:59 109

原创（二叉树）11. 一颗二叉树是否是二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:示例 2:题解思路中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，说明满足 BST，继续遍历；否则直接返回 false实现代码class Solution { int pre = Integer.MIN_VALUE; public boolean i

2020-09-05 12:13:50 101

原创（二叉树）剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。示例 1:输入: root = [3,1,4,null,2], k = 1示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 3限制：1 ≤ k ≤ 二叉搜索树元素个数题解思路二叉搜索树的中序遍历为递增序列所以二叉搜索树的中序遍历倒序为递减序列。因此，求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。实现代码class Solution { i

2020-09-05 09:57:59 87

原创（二叉树）110. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。示例 1:给定二叉树 [3,9,20,null,null,15,7]返回 true 。示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4]返回 false 。题解思路若左右子树的深度差的绝对值小于等于1，则返回当前节点的深度若左右子树的深度差的绝对之后大于1，则返回-1实现代码class Solution { public bo

2020-09-05 09:30:10 114

原创（数组）6. 无序数组中找出第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题解思路每次切分操作总能排定一个元素，还能够知道这个元素它最终所在的位置，这样每经过一次 partition（切分）操作就能缩小搜索的范围实现代码public class Solution { public

2020-09-04 23:52:36 566

原创（数组）8. 快速排序

题解思路先对二维数组按区间左端点大小排序，然后依次入栈若栈内区间右端点小于当前区间左端点，则两个区间无重叠部分，直接将当前区间入栈若栈内区间右端点大于当前区间左端点，则说明两区间存在重叠部分，更新栈内区间右端点值，取最大实现代码public static void quickSort(int[] array) { int len; if(array == null || (len = array.length) == 0 || len

2020-09-03 14:56:59 782

原创（数组）2. 合并区间（leedcode.56）（快手）

给出一个区间的集合，请合并所有重叠的区间。示例 1:输入: intervals = [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2:输入: intervals = [[1,4],[4,5]]输出: [[1,5]]解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。题解思路先对二维数组按区间左端点大小排序，然后依次入栈若栈内区间右端点小

2020-09-03 11:48:02 190

原创（数组）15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[[-1, 0, 1],[-1, -1, 2]]题解思路首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nu

2020-09-03 11:05:57 168

原创（二叉树）15. 二叉树剪枝

给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。返回移除了所有不包含 1 的子树的原二叉树。( 节点 X 的子树为 X 本身，以及所有 X 的后代。)示例1:输入: [1,null,0,0,1]输出: [1,null,0,null,1]解释:只有红色节点满足条件“所有不包含 1 的子树”。右图为返回的答案。示例2:输入: [1,0,1,0,0,0,1]输出: [1,null,1,null,1]示例3:输入: [1,1,0,1,1,0,1,0]输出:

2020-08-31 11:42:04 218

原创（二叉树）3. 二叉树最近公共父节点

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]示例 1:输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3解释: 节点 5 和节点 1

2020-08-29 10:39:26 616

原创（二叉树）14. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。示例 :给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。注意：两结点之间的路径长度是以它们之间边的数目表示。题解思路直径=max（当前节点到任意节点之间的最大节点数-1）当前节点到任意节点之间的最大节点数=当前节点左子树最大深度

2020-08-29 10:10:28 102

原创（二叉树）1. 求二叉树第K层节点数

题目内容如标题所示题解思路实现代码public class Solution { public int kNum(TreeNode root, int k) { if (root == null || k < 0) { return 0; } if (k == 1) { return 1; } return kNum(root.left, k - 1) + kN

2020-08-29 00:33:06 152

原创（二叉树）4. 二叉树的非递归中序遍历

给定一个二叉树，返回它的中序遍历。示例:输入: [1,null,2,3]1\2/3输出: [1,3,2]题解思路递归的调用过程是不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程。我们在迭代实现时，就可以用栈来模拟上面的调用过程。实现代码class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> re

2020-08-29 00:09:46 120

原创（二叉树）13. 求二叉搜索树的任意两个节点值之差的最小值（绝对值）

给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。示例：输入: root = [4,2,6,1,3,null,null]输出: 1解释:注意，root是树节点对象(TreeNode object)，而不是数组。给定的树 [4,2,6,1,3,null,null] 可表示为下图: 4 / \ 2 6 / \ 1 3 最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。题解思路因为在二叉搜索树中，

2020-08-28 23:31:19 900

原创（二叉树）7. 二叉树中的最大路径和

8. 二叉树中的最大路径和给定一个非空二叉树，返回其最大路径和。本题中路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。示例 1:输入: [1,2,3] 1 / \ 2 3输出: 6示例 2:输入: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7输出: 42题解思路 1. 从 dfs(-10) 开始， 1.1 dfs

2020-08-28 22:56:00 226