- 博客(74)
- 收藏
- 关注
RSS订阅原创 子数组的最大累加和（简单但想不到）也是容许变小但保存最大值
描述给定一个数组arr，返回子数组的最大累加和例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.题目保证没有全为负数的数据[要求]时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)示例1class Solution {public: /** * max sum of the subarray * @param arr int整型vector the array
2021-08-19 17:09:19
105
原创 二叉搜索树中的众数（1.我用占空间坐的，而且针对所有二叉树。技术包括map放到vector中排序等2.我最喜欢的有序重复边走边找3.直接在dfs过程中拿值（第3种要二刷））
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。假定 BST 有如下定义：结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的值左子树和右子树都是二叉搜索树例如：给定 BST [1,null,2,2],返回[2].提示：如果众数超过1个，不需考虑输出顺序进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）/** * Definition for a binary tree node
2021-07-26 16:06:44
93
原创 二叉树的所有路径（自己想的回溯解决，通常说用dfs一样）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *
2021-07-26 14:14:19
168
原创 平衡二叉树的判断（哈哈哈哈自己写的，cool，先写一次的条件，不直接返回true再直接返回往下的）
给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。示例 1：输入：root = [3,9,20,null,null,15,7]输出：true示例 2：输入：root = [1,2,2,3,3,null,null,4,4]输出：false示例 3：输入：root = []输出：true提示：树中的节点数在范围 [0, 5000] 内-104 <= Node.val <= 1
2021-07-26 13:44:23
116
原创 2021-07-26
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。示例 1：输入：nums = [-10,-3,0,5,9]输出：[0,-3,9,-10,null,5]解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：示例 2：输入：nums = [1,3]输出：[3,1]解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。提示
2021-07-26 11:37:02
59
原创 左叶子之和（按之前的规律三个节点不能完全解决的情况下再加，想了一下一遍过，绝绝子）
计算给定二叉树的所有左叶子之和。示例：/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr),
2021-07-26 11:21:03
49
原创 翻转二叉树（和比较值无关的时候就不用判断左右子树是否为NULL）
翻转一棵二叉树。示例：输入：输出：而且至少要把最关键的那一步做了。再递归。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) :
2021-07-23 09:38:07
65
原创 后序遍历（迭代版）
给定一个二叉树，返回它的 后序 遍历。示例:进阶: 递归算法很简单，你可以通过迭代算法完成吗？解:while( 栈非空){if( p 非空){}else{}}/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(null
2021-07-22 13:48:56
1012
原创 对称二叉树（看图，不是简单一个左右子树的比较，而是实际上涉及两棵树，但也要从当做只有三个节点开始看）
给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullpt
2021-07-22 09:49:58
68
原创 二叉树的最小深度（比最大复杂一点因为需要忽略空节点，不忽略的话会算进去就变成最小了+深度指的是到根节点，而不是到空节点的距离）
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。示例 1：输入：root = [3,9,20,null,null,15,7]输出：2示例 2：输入：root = [2,null,3,null,4,null,5,null,6]输出：5提示：树中节点数的范围在 [0, 105] 内-1000 <= Node.val <= 1000/** * Definition for a binary tree
2021-07-21 17:35:49
83
原创 路径总和（一遍过，稍微想一下即可）
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。叶子节点 是指没有子节点的节点。示例 1：输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22输出：true示例 2：输入：root = [1,2,3], targetSum = 5输出：false示例 3：输入：root = [
2021-07-21 17:32:52
53
原创 快排用随机
给你一个整数数组nums，请你将该数组升序排列。示例 1：输入：nums = [5,2,3,1]输出：[1,2,3,5]示例 2：输入：nums = [5,1,1,2,0,0]输出：[0,0,1,1,2,5]提示：1 <= nums.length <= 50000-50000 <= nums[i] <= 50000class Solution {public: vector<int> sortArray(vector...
2021-06-10 18:43:43
71
原创 数组中的第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 ≤ 数组的长度。①快排。写出快排后再修改，一次过。class Solution {public: int findKthLargest(vec.
2021-06-10 11:24:50
198
原创 栈的压入、弹出序列（留存，理解之后代码很好写）
题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）示例1输入复制[1,2,3,4,5],[4,3,5,1,2]返回值复制false思路：每次入栈一个元素后，都要判断一下栈顶元素是不是当前出栈序列 popSeque
2021-04-09 13:44:06
116
原创 用两个栈实现队列（留存，自己过，注意把2出完再说）
题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。自己过，背：class Solution{public: void push(int node) { stack1.push(node); } int pop() { int res; if(stack2.empty()) { while(!stack1.empty())
2021-04-07 17:14:09
46
原创 合并两个排序的链表（弱项）
题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。示例1输入复制{1,3,5},{2,4,6}返回值复制{1,2,3,4,5,6}
2021-04-07 16:51:15
55
原创 复杂链表的复制（什么是复杂链表？难点在哪？）
题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回原参数中的节点引用，否则判题程序会直接返回空）问题：random指向一个随机的ListNode*，这个随机值可能没有创建，所以依次复制会出现错误。 random的复制成了难题。解题思路第一步，在每个节点的后面插入复制的节点。第二步，对复制节点的 random 链接进行赋值。.
2021-04-07 16:50:43
83
原创 删除链表中重复的节点（二刷二刷，经典，递归实现，看代码更清晰）
题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5示例1输入复制{1,2,3,3,4,4,5}返回值复制{1,2,5}每次删除头上的或者返回头：（看代码更清晰）/*struct ListNode { int val; struct ListNode *next;
2021-04-06 20:34:52
133
原创 两个链表的第一个公共节点（理解之后自写，简洁，一遍过）
题目描述输入两个链表，找出它们的第一个公共结点。解题思路：设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。非常简洁：/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNo
2021-04-06 20:17:11
72
原创 反转链表（更新我更喜欢的命名方法）
题目描述输入一个链表，反转链表后，输出新链表的表头。示例1输入复制{1,2,3}返回值复制{3,2,1}/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* ReverseList(ListNode* pHead) {
2021-04-06 20:01:33
87
原创 二叉树的最近公共祖先
前文：二叉搜索树的最近公共祖先当然也能用本文的方法直接解。给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output: 3Explanation: The LCA of n.
2021-04-06 19:48:02
54
原创 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”例如，给定如下二叉搜索树:root =[6,2,8,0,4,7,9,null,null,3,5]示例 1:输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6解释:...
2021-04-06 19:39:47
133
原创 链表中环的入口节点
题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。分为两步：①如何判断有环的存在？在追及问题中，我们可以用两个速度不同的物体从同一地点出发，如果相遇则证明存在环（可用反证法证明，若不存在环，则速度不同的物体从同一地点出发则一定不会相遇），因此可以类比过来，定义两个指针fast、slow，令两指针以不同速度向后指，则相遇时证明有环存在，若fast指向NULL，则不存在环。②怎么找到环的入口结点？首先说方法：在问题一中两指针相遇后，让一个指针从头结点开始，另一
2021-04-06 19:34:36
109
原创 链表倒数第k个节点（留存。问题简单但奇怪，这编译器好像有问题）
题目描述输入一个链表，输出该链表中倒数第k个结点。示例1输入复制1,{1,2,3,4,5}返回值复制{5}/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* FindKthToTail(ListNode* pListHead, un
2021-04-06 19:16:00
30
原创 从尾到头打印单链表并存起来（递归
题目描述输入一个链表，按链表从尾到头的顺序返回一个ArrayList。示例1输入复制{67,0,24,58}返回值复制[58,24,0,67]简洁写法：/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) :* val(x), next(NULL) {* }* };*/
2021-04-06 18:39:04
43
原创 平衡二叉树的判断（一路做下来一遍过，用到前面判断二叉树高度的一句递归）
题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。示例1输入复制{1,2,3,4,5,6,7}返回值复制true自写法，一遍过：class Solution {public: bool IsBalanced_Solutio
2021-04-04 20:11:08
80
原创 【经典】二叉树深度（一句话）
题目描述输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。示例1输入复制{1,2,3,4,5,#,6,#,#,7}返回值复制4（我）①想到层次遍历，每进入一层就count++，代码长。/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : v.
2021-04-04 19:45:18
60
原创 二叉搜索树的第k个结点
题目描述给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。示例1输入复制{5,3,7,2,4,6,8},3返回值复制{4}说明按结点数值大小顺序第三小结点的值为4 ①我写的需要多一个内存的：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : va
2021-04-04 19:15:13
80
原创 二叉搜索树转双向链表
题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。题意简单例子图示：看这个例子涵盖情况较多：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/class Solut..
2021-04-04 18:23:31
1114
原创 二叉树中和为某一值的路径（回溯法void backtracking(vector＜vector＜int＞＞&res；vector＜int＞ middle；)）
题目描述输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。示例1输入复制{10,5,12,4,7},22返回值复制[[10,5,7],[10,12]]示例2输入复制{10,5,12,4,7},15返回值复制[]/*struct TreeNode { int val; struct TreeNode *left; s.
2021-04-04 16:57:07
136
原创 二叉搜索数的后序遍历序列（对后续遍历的理解不深）
题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）示例1输入复制[4,8,6,12,16,14,10]返回值复制true注意看注释： //序列最后一个元素是根节点，而二叉搜索树的根节点左边的序列值比根小，右边的比根大。 //根据这个特性，将序列分为两半，左边序列的值比根节点小，右边序列的值比根节点...
2021-04-04 16:28:27
103
原创 按之字形顺序打印二叉树（易错）（因为到了只变一下，整体的还是原来的那棵树的进入顺序，直接改变原来的进入顺序会乱）
题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。示例1输入复制{8,6,10,5,7,9,11}返回值复制[[8],[10,6],[5,7,9,11]]分析：（易错）（因为到了只变一下，整体的还是原来的那棵树的进入顺序，直接改变原来的进入顺序会乱）直接改变原来的进入顺序会错误打印成[[8],[10,6],[9,11,5,7]]。可以引入一个count变量
2021-04-04 12:24:16
60
原创 把二叉树打印成多行（带层次的BFS，代码在while基础上加个for）
题目描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。示例1输入复制{8,6,10,5,7,9,11}返回值复制[[8],[6,10],[5,7,9,11]]自己写：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL)
2021-04-04 11:49:49
56
原创 从上往下打印二叉树（BFS一遍过）
题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。示例1输入复制{5,4,#,3,#,2,#,1}返回值复制[5,4,3,2,1]/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/class Solution {pub
2021-04-04 11:32:50
127
原创 对称的二叉树（对称：与自己的镜像二叉树相同）
题目描述请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。示例1输入复制{8,6,6,5,7,7,5}返回值复制true示例2输入复制{8,6,9,5,7,7,5}返回值复制false/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; Tre
2021-04-04 11:31:08
93
原创 二叉树的镜像（简单。观察镜像即左右子树都交换）
题目描述操作给定的二叉树，将其变换为源二叉树的镜像。输入描述:二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5自己一遍过：/*struct TreeNode { int val; struct TreeNod
2021-04-02 11:36:12
146
原创 树的子结构
题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）示例1输入复制{8,8,#,9,#,2,#,5},{8,9,#,2}返回值复制true淘汰：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }
2021-04-01 22:37:36
46
原创 二叉树的下一个节点
题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。两种情况情况1.这种情况下得找自己祖先是哪个隔代祖先的左子树。如果一直是右子树到了根节点，那说明到头了，下一个是null。情况2.理解:※ 右子树的最左节点。/*struct TreeLinkNode { int val; struct TreeLinkNode *left; struct TreeLinkNode.
2021-04-01 21:02:14
43
原创 （自己写，规范）根据前序遍历和中序遍历重建二叉树
题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。示例1输入复制[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]返回值复制{1,2,5,3,4,6,7}/** * Definition for binary tree * struct TreeNode {
2021-04-01 19:40:31
72
原创 构建乘积数组
题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。示例1输入复制[1,2,3,4,5]返回值复制
2021-03-30 23:05:47
43
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人