二叉树leetcode题单
更多的题目：二叉树leetcode题单-labuladong专项训练
| 分类 | 相关题号 | done | 代码 | 备注 |
|---|---|---|---|---|
| 二叉树遍历 | 144. 二叉树的前序遍历 | ✅ | 递归、迭代，注意迭代的写法：右孩子先进栈 | |
| ☆二叉树遍历 | 94. 二叉树的中序遍历 | ✅ | 递归、迭代，注意迭代的写法 | |
| 二叉树遍历 | 145. 二叉树的后序遍历 | ✅ | 递归、迭代，注意迭代的写法：左孩子先进栈，最后要翻转 | |
| 二叉树遍历 | 102. 二叉树的层序遍历 | ✅ | 队列 | |
| 二叉树遍历 | 226. 翻转二叉树 | ✅ | 前序or后序遍历，不能用中序 | |
| 二叉树遍历 | 101. 对称二叉树 | ✅ | compare:左外vs右外、左内vs右内 | |
| 104. 二叉树的最大深度 | ✅ | 1+max(左子树深度,右子树深度)，也可以用层次遍历 | ||
| ☆ | 111. 二叉树的最小深度 | ✅ | 此题递归解法有陷阱，1+min(minDepth(左),minDepth(右)) 如果左、右孩子都为nil，返回1，如果左为nil，返回右的最小深度，如果右为nil，返回左的最小深度，如果左右都不为nil，返回 1+min(minDepth(左),minDepth(右))； 迭代解法：层次遍历，遇到第一个叶子节点即是最小深度 |
|
| ☆ | 110. 平衡二叉树 | ✅ | 获取深度，如果不平衡返回-1，递归中判断如果有-1的情况直接返回，否则返回1+max(左子树深度,右子树深度)，也可以用层次遍历 | |
| DFS | 257. 二叉树的所有路径 | ✅ | 回溯 | |
| DFS | 112. 路径总和 | ✅ | 回溯 | |
| DFS | 113. 路径总和 II | ✅ | 回溯 | |
| 构造二叉树 | 106. 从中序与后序遍历序列构造二叉树 | ✅ | 注意边界即可 | |
| 构造二叉树 | 105. 从前序与中序遍历序列构造二叉树 | ✅ | 注意边界即可 | |
| ☆遍历 | 617. 合并二叉树 | ✅ | 同时遍历2棵树，孩子nil节点处理，root.Val相加 | |
| 二分查找 | 700. 二叉搜索树中的搜索 | ✅ | ||
| ☆中序遍历+pre节点 | 98. 验证二叉搜索树 | ✅ | 迭代、递归都可，注意如何保存pre节点 | |
| ☆中序遍历+pre节点 | 530. 二叉搜索树的最小绝对差 | ✅ | 迭代、递归都可，注意如何保存pre节点 | |
| ☆中序遍历+pre节点 | 501. 二叉搜索树中的众数 | ✅ | 迭代、递归都可，注意如何保存pre节点，注意计数的变化、何时清空结果集 | |
| ☆ | 236. 二叉树的最近公共祖先 | ✅ | 注意递归终止条件包含root = p or q;左边找一下返回n1,右边找一下返回n2，处理n1、n2同时为nil和有一个为nil的场景 | |
| 235. 二叉搜索树的最近公共祖先 | ✅ | |||
| 701. 二叉搜索树中的插入操作 | ✅ | 插入到叶子节点上 | ||
| ☆ | 450. 删除二叉搜索树中的节点 | ✅ | 递归函数有返回值，利用返回值；分为5中情况：1.未找到 2.是叶子节点，直接删 3.左孩子为空，右孩子补到当前节点上 4.右孩子为空，左孩子补到当前节点上 5.左右孩子都不为空，左孩子插到右孩子的最左边 | |
| ☆ | 669. 修剪二叉搜索树 | ✅ | 递归函数有返回值，注意利用返回值；root.Val < low时，左孩子都不要了；root.Val > right时，右孩子都不要了 | |
| 108. 将有序数组转换为二叉搜索树 | ✅ | 类似二分查找 |
| 分类 | 相关题号 | done | 代码 | 备注 |
|---|---|---|---|---|
| 组合:选k个数 | 77. 组合 | ✅ | 1.startIndex 2.剪枝优化：已选择+剩余元素<k时 |
|
| 组合:从1-9中选和为n的k个数 | 216. 组合总和 III | ✅ | 1.startIndex 2.剪枝优化：已选择+剩余元素<k时 |
|
| 组合:从候选数组中选和为target的所有组合 | 39. 组合总和 | ✅ | 1.startIndex 2.对target做减操作，则不用累加 3.剪枝：排序+如果target减操作后小于0，则跳出循环 |
|
| 组合:从重复元素的候选数组中选和为target的所有组合 | 40. 组合总和 II | ✅ | 1.startIndex 2.对target做减操作，则不用累加 3.排序+同层去重 4.剪枝:如果target减操作后小于0，则跳出循环 |
|
| 17. 电话号码的字母组合 | ✅ | |||
| 131. 分割回文串 | ✅ | 1.startIndex 2.判断回文 |
||
| 93. 复原 IP 地址 | ✅ | 1.选择3个有效数字后，直接判断剩余的1个是否合法，可作为递归终止条件 | ||
| 子集 | 78. 子集 | ✅ | 1.startIndex | |
| 子集:输入数组有重复元素 | 90. 子集 II | ✅ | 1.startIndex 2.排序+同层去重 |
|
| 491. 递增子序列 | ✅ | 1.startIndex 2.同层去重使用局部变量 |
||
| 全排列 | 46. 全排列 | ✅ | 1.标记数组 | |
| 全排列 | 47. 全排列 II | ✅ | 1.标记数组 2.同层去重 |
|
| 51. N 皇后 | ✅ | |||
| 37. 解数独 | ||||
| 332. 重新安排行程 |
动态规划leetcode题单 更多题目：动态规划leetcode题单-花花酱
| 分类 | 相关题号 | done | 代码 | 备注 |
|---|---|---|---|---|
| 509. 斐波那契数 | ✅ | |||
| 70. 爬楼梯 | ✅ | |||
| 746. 使用最小花费爬楼梯 | ✅ | 第一步不需要花费体力值，最后一步需要花费 | ||
| 62. 不同路径 | ✅ | 二维dp，可压测成2行；还有数论方法 | ||
| 63. 不同路径 II | ✅ | 必须使用二维dp | ||
| ☆ | 343. 整数拆分 | ✅ | 最值是 dp[i]=max(dp[i], dp[i-j]*j, (i-j)*j), 不要遗忘(i-j)*j 此题有贪心解法 |
|
| 96. 不同的二叉搜索树 | ✅ | 选择一个根节点，左子树的数量*右子树的数量，注意是乘法 | ||
| 0-1背包 | 416. 分割等和子集 | ✅ | 转化成挑选元素等于total/2的背包问题，物品重量和价值都是nums[i],如果最终重量等于价值，则存在 | |
| ☆0-1背包 | 494. 目标和 | ✅ | 解法思路： left - right = target => left - (sum-left) = target => left = (sum+target)/2 ，即从数组中选出和为left的有多少种方法。 dp数组的定义和普通背包问题略有不同 |
|
| ☆0-1背包 | 474. 一和零 | ✅ | 背包重量是二维的 | |
| 完全背包，求组合数 | 518. 零钱兑换 II | ✅ | 如果单纯问“能否”凑成总和，遍历物品、遍历背包容量是没有顺序要求的。但是本题求组合数 dp[j]：兑换金额为 amount 的时候，有多少种组合，等于所有 dp[j-coin] 之和 |
|
| 完全背包，求排列数 | 377. 组合总和 Ⅳ | ✅ | 本题求排列数 如果求组合数，外层for循环遍历物品、内层for循环遍历背包 如果求排列数，外层for循环遍历背包、内层for循环遍历物品 |
|
| 完全背包，最少硬币数 | 322. 零钱兑换 | ✅ | 求最小，组合和排列都可以，物品在外层效率高一些 | |
| 完全背包，最少数量 | 279. 完全平方数 | ✅ | 和求最少硬币数一样 | |
| 完全背包，求排列 | 139. 单词拆分 | ✅ | 完全背包问题求排列，所以背包重量在外层循环 | |
| 股票买卖 | 121. 买卖股票的最佳时机 | ✅ | dp[i][0] 表示第i天持有股票的最大收益（当天买入或者前一天就持有）， dp[i][1]表示不持有股票的最大收益（当天卖出，或者前一天就没持有) 可用贪心算法：找曲线最低点和最高点 |
|
| 股票买卖,可多次交易 | 122. 买卖股票的最佳时机 II | ✅ | dp[i][0] 表示第i天持有股票的最大收益， dp[i][1]表示不持有股票的最大收益 可用贪心算法：多次找曲线最低点和最高点 |
|
| 股票买卖,最多2次交易 | 123. 买卖股票的最佳时机 III | ✅ | hard，有点绕 | |
| 股票买卖,最多k次交易 | 188. 买卖股票的最佳时机 IV | ✅ | hard,可以从2次交易的推导过来 | |
| 股票买卖,有冷冻期 | 309. 最佳买卖股票时机含冷冻期 | ✅ | 4种状态 | |
| 股票买卖,有手续费 | 714. 买卖股票的最佳时机含手续费 | ✅ | ||
| 最长问题，输入单个数组 | 300.最长递增子序列 | ✅ | ||
| 最长问题，输入单个数组 | 674. 最长连续递增序列 | ✅ | ||
| 编辑距离，最长问题，输入2个字符串(数组) | 718. 最长重复子数组 | ✅ | ||
| 编辑距离(只删)，最长问题 | 1143. 最长公共子序列 | ✅ | ||
| 编辑距离(只删)，最长问题 | 1035.不相交的线 | ✅ | ||
| 53. 最大子数组和 | ✅ | |||
| 编辑距离(只删) | 392.判断子序列 | ✅ | ||
| 编辑距离(只删) | 115.不同的子序列 | ✅ | ||
| 编辑距离(只删) | 583. 两个字符串的删除操作 | ✅ | ||
| 编辑距离(增、删、改) | 72. 编辑距离 | ✅ | ||
| 647. 回文子串 | 还有双指针的解法 |
| 分类 | 相关题号 | done | 代码 | 备注 |
|---|---|---|---|---|
| 455.分发饼干 | ✅ | easy，排序 | ||
| 376.摆动序列 | ✅ | 找峰、谷 | ||
| 53.最大子序和 | ✅ | easy | ||
| 122.买卖股票的最佳时机 II | ✅ | 1.可以使用贪心（找低谷和峰值） 2.使用动态规划 |
||
| 55.跳跃游戏 | ✅ | 使用cover解，注意终止条件 | ||
| 45.跳跃游戏 II | ✅ | 使用cover、nextCover，转化的时候+1操作 | ||
| 1005.K 次取反后最大化的数组和 | ✅ | 按照绝对值排序，从后往前遍历，将负数取反；如果k还大于0且k%2==1，则取最小的正数取反 | ||
| 134.加油站 | ✅ | 大前提：油量和>使用和；i从0累加resti,和为curSum，一旦curSum小于0说明[0,i]区间的位置不能作为起始位置，起始维中从i+1开始，再重新计算curSum。为什么从i+1开始？i之前有多少负数，i之后就有对应的正数（因为大前提） | ||
| 135.分发糖果 | hard，初始化结果数组为1，先从左往右遍历，如果右边孩子评分搞，则candyVec[i]=candyVec[i-1]+1,然后从右往左遍历，如果左边孩子评分高，则candyVec[i]=max(candyVec[i+1]+1, candyVec[i])，最后糖果数量相加 | |||
| 860.柠檬水找零 | ✅ | easy | ||
| 406.根据身高重建队列 | ✅ | 有点难度 | ||
| 452.用最少数量的箭引爆气球 | ✅ | 无交集的数量 => 放箭的数量，先排序 | ||
| ☆ | 435.无重叠区间 | ✅ | 有点难度，按照右边界排序，前一个的end和下一个的start没有重合，说明非交叉，每次取非交叉区间的时候，都是可右边界最小的来做分割点。区间总数-非交叉区间的个数 => 要移除的区间个数 | |
| 763.划分字母区间 | ✅ | 1.先遍历一遍找到每个字母的最远边界；2.再次遍历，如果下标和最远边界相等，则是一个分界点 | ||
| 56.合并区间 | ✅ | 排序+合并 | ||
| 738.单调递增的数字 | ✅ | 1.如果strNum[i-1]>strNum[i],则strNum[i-1]=strNum[i-1]-1, strNum[i]=9;2.要从后往前遍历;3.一旦出现i变9的情况，i后边的数字都要直接变9 | ||
| 714.买卖股票的最佳时机含手续费 | ✅ | 参考：122. 买卖股票的最佳时机 II 的动归解法 1.可以使用贪心（难理解） 2.使用动态规划 |
||
| 968.监控二叉树 | hard |
| 分类 | 相关题号 | done | 代码 | 备注 |
|---|---|---|---|---|
| 数组 | 704.二分查找 | ✅ | easy | |
| 数组 | 34.在排序数组中查找元素的第一个和最后一个位置 | ✅ | 二分查找变种题，不用判断边界，使用pre变量 | |
| 数组 | 27.移除元素 | ✅ | easy | |
| 数组 | 977.有序数组的平方 | ✅ | easy | |
| 数组 | 209.长度最小的子数组 | ✅ | 双指针 | |
| 数组 | 59.螺旋矩阵 II | ✅ | 坚持所有循环都是左开右闭 | |
| 数组 | 31.下一个排列 | ✅ | 跟排列有点关系 | |
| 数组 | 169.多数元素 | ✅ | ||
| ---- | ||||
| 链表 | 203.移除链表元素 | ✅ | easy | |
| 链表 | 707.设计链表 | ✅ | ||
| 链表 | 206.反转链表 | ✅ | easy | |
| 链表 | 24.两两交换链表中的节点 | ✅ | ||
| 链表 | 19.删除链表的倒数第 N 个结点 | ✅ | fast走n+1步 | |
| 链表 | 面试题 02.07.链表相交 | ✅ | easy | |
| 链表 | 142.环形链表 II | ✅ | ||
| ---- | ||||
| 哈希表 | 242.有效的字母异位词 | ✅ | easy | |
| 哈希表 | 349.两个数组的交集 | ✅ | easy | |
| 哈希表 | 202.快乐数 | ✅ | easy | |
| 哈希表 | 1.两数之和 | ✅ | easy | |
| 哈希表 | 15. 三数之和 | ✅ | 通用解法，参考：https://mp.weixin.qq.com/s/fSyJVvggxHq28a0SdmZm6Q | |
| 哈希表 | 18. 四数之和 | ✅ | 通用解法，参考：https://mp.weixin.qq.com/s/fSyJVvggxHq28a0SdmZm6Q | |
| 哈希表 | 454.四数相加 II | ✅ | ||
| 哈希表 | 383.赎金信 | ✅ | easy | |
| ---- | ||||
| 字符串 | 344.反转字符串 | ✅ | easy 使用双指针 |
|
| 字符串 | 541.反转字符串 II | ✅ | ||
| 字符串 | 剑指 Offer 05.替换空格 | ✅ | easy | |
| 字符串 | 151.翻转字符串里的单词 | ✅ | ||
| 字符串 | 剑指 Offer 58 - II.左旋转字符串 | ✅ | easy | |
| 字符串 | 28.实现 strStr() | KMP | ||
| 字符串 | 459.重复的子字符串 | KMP |
| 分类 | 相关题号 | done | 代码 | 备注 |
|---|---|---|---|---|
| 232. 用栈实现队列 | ✅ | |||
| 225. 用队列实现栈 | ✅ | |||
| 栈 | 20. 有效的括号 | ✅ | ||
| 栈 | 150. 逆波兰表达式求值 | ✅ | ||
| 单调队列 | 239. 滑动窗口最大值 | ✅ | hard,push x的时候，将x与队尾元素比较，如果队尾元素小于x，则不断删除队尾元素，使队列保持单调递减；pop的时候将nums[i-k+1]和队头元素比较，相等时才删除 | |
| 单调栈 | 496. 下一个更大元素 I | ✅ | ||
| 单调栈 | 739. 每日温度 | ✅ | ||
| 单调栈 | 503. 下一个更大元素 II | ✅ | ||
| 优先队列 | 347. 前 K 个高频元素 | ✅ | 前k个高频元素（不是大小的top k），使用partition的思想，堆的方式代码不好记 |
| 分类 | 相关题号 | done | 代码 | 备注 |
|---|---|---|---|---|
| 双指针 | 42. 接雨水 | ✅ | 方法一：提前计算好lmax、rmax数组，空间复杂度O(n)；方法二：同步计算lmax和rmax，空间复杂度O(1) | |
| 双指针 | 11. 盛最多水的容器 | ✅ | 计算面积，求最大 |
| 分类 | 相关题号 | done | 代码 | 备注 |
|---|---|---|---|---|
| 前缀树 | 208. 实现 Trie (前缀树) | ✅ | ||
| 前缀树 | 648. 单词替换 | |||
| 前缀树 | 211. 添加与搜索单词 - 数据结构设计 | |||
| 前缀树 | 677. 键值映射 | |||