很多时候不懂事

📝 题目描述 题目链接：腐烂的橘子 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： 值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。 示例： 示例 1： 12输入：grid = [[2,1,1],[1,1,0],[0,1,1]]输出：4 示例 2： 123输入：grid = [[2,1,1],[0,1,1],[1,0,1]]输出：-1解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。 示例 3： 123输入：grid = [[0,2]]输出：0解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。 提示： m == grid.length n == grid[i].length 1 <= m, n <= 10 grid[i][j] 仅为 0、1 或 2 💡 解题思路 方法一：多源广度优先搜索 这道题本质...

📝 题目描述 题目链接：岛屿数量 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 示例： 12345678910111213141516171819示例 1：输入：grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0']]输出：1示例 2：输入：grid = [ [...

📝 题目描述 题目链接：二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其 最大路径和 。 示例： 示例 1： 123输入：root = [1,2,3]输出：6解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6 示例 2： 123输入：root = [-10,9,20,null,null,15,7]输出：42解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42 提示： 树中节点数目范围是 [1, 3 * 10^4] -1000 <= Node.val <= 1000 💡 解题思路 方法一：递归 首先不要被“路径还能横着走”吓到。 思考：参考“最大子数组和”，对于一个节点，如何计算它的单边最大贡献值？ 我们思考从上到下单走一条路的情况，也即只选择它的左右...

📝 题目描述 题目链接：二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 示例： 示例 1： 123输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2： 123输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出：5解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3： 12输入：root = [1,2], p = 1, q = 2输出：1 提示： 树中节点数目在范围 [2, 105] 内 -10^9 <= Node.val <= 10^9 所有 Node.val 互不相同 p != q p 和 q 均存在于给定...

📝 题目描述 题目链接：路径总和 III 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 示例： 示例 1： 123输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8输出：3解释：和等于 8 的路径有 3 条，如图所示。 示例 2： 12输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出：3 提示： 二叉树的节点个数的范围是 [0,1000] -10^9 <= Node.val <= 10^9 -1000 <= targetSum <= 1000 💡 解题思路 方法一：前缀和✅️ 实际上就是“和为K的子数组”的变体。 定义节点的前缀和为：由根结点到当前结点的路径上所有节点的和。我们利用先序遍历二叉树，记录下根节点...

📝 题目描述 题目链接：从前序与中序遍历序列构造二叉树 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的 先序遍历， inorder 是同一棵树的 中序遍历，请构造二叉树并返回其根节点。 示例： 示例 1： 12输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出: [3,9,20,null,null,15,7] 示例 2： 12输入: preorder = [-1], inorder = [-1]输出: [-1] 提示： 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder 均 无重复 元素 inorder 均出现在 preorder preorder 保证 为二叉树的前序遍历序列 inorder 保证 为二叉树的中序遍历序列 💡 解题思路 方法一：递归 ...

📝 题目描述 题目链接：二叉树展开为链表 给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。 示例： 示例 1： 12输入：root = [1,2,5,3,4,null,6]输出：[1,null,2,null,3,null,4,null,5,null,6] 示例 2： 12输入：root = []输出：[] 示例 3： 12输入：root = [0]输出：[0] 提示： 树中结点数在范围 [0, 2000] 内 -100 <= Node.val <= 100 💡 解题思路 方法一：先序遍历 最容易想到的方法，既然题目要求我们先序遍历，那么我们就使用迭代法进行先序遍历，一边遍历一边连接节点。 方法二：寻找前驱节点 前序遍历过程中需要使用栈存储节点。有没有空间复杂度是 O(1) 的做法呢？ 注意到前序遍历访问各节点的顺序是 根节点、左子树、右子树。 如果一个 节点A 的左子节...

📝 题目描述 题目链接：二叉树的右视图 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例： 示例 1： 12输入：root = [1,2,3,null,5,null,4]输出：[1,3,4] 示例 2： 12输入：root = [1,2,3,4,null,null,null,5]输出：[1,3,4,5] 示例 3： 12输入：root = [1,null,3]输出：[1,3] 示例 4： 12输入：root = []输出：[] 提示： 二叉树的节点个数的范围是 [0,100] -100 <= Node.val <= 100 💡 解题思路 方法一：深度优先搜索 我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。 这样一来，我们可以存储在每个深度访问的第一个结点，一旦我们知道了树的层数，就可以得到最终的结果数组。 上图表示了问题的一个实例。红色结点自上而下组成答案，边缘以访问顺序标号。 方法二：广度优先搜索 比较容...

📝 题目描述 题目链接：二叉搜索树中第 K 小的元素 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。 示例： 示例 1： 12输入：root = [3,1,4,null,2], k = 1输出：1 示例 2： 12输入：root = [5,3,6,2,4,null,null,1], k = 3输出：3 提示： 树中的节点数为 n 1 <= k <= n <= 10^4 0 <= Node.val <= 104 💡 解题思路 方法一：中序遍历 还记得“将有序数组转换为二叉搜索树”吗？在这里面我们提到： 二叉搜索树的中序遍历得到的值构成的序列一定是升序的。 据此，我们可以对题目中的二叉树进行中序遍历，第 k 个值就是我们要找的答案。 ★方法二：记录子树的结点数 在方法一中，我们之所以需要中序遍历前 k 个元素，是因为我们不知道子树的结点数量，不得不通过遍历子树的方式来获知。 因此，我们可以记录下以每个结点为根结点的子树的结点数，并在查找第 k 小的值时，使用如下方法...

📝 题目描述 题目链接：验证二叉搜索树 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下： 节点的左只包含 严格小于 当前节点的数； 节点的右子树只包含 严格大于 当前节点的数； 所有左子树和右子树自身必须也是二叉搜索树。 子树：treeName 树中的一个节点及其所有子孙节点所构成的树称为 treeName 的 子树。 示例： 示例 1： 12输入：root = [2,1,3]输出：true 示例 2： 123输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。 提示： 树中节点数目范围在[1, 10^4] 内 -2^31 <= Node.val <= 2^31 - 1 💡 解题思路 方法一：中序遍历 还记得“将有序数组转换为二叉搜索树”吗？在这里面我们提到： 二叉搜索树的中序遍历得到的值构成的序列一定是升序的。 据此，我们可以对题目中的二叉树进行中序遍历，检查得到的值是否是严格升序的。 这里要注意我们需使用 int64_...