很多时候不懂事

📝 题目描述 题目链接：路径总和 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_...

📝 题目描述 题目链接：将有序数组转换为二叉搜索树 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡二叉搜索树。 二叉搜索树：左子树上所有节点的值都小于根节点的值；右子树上所有节点的值都大于根节点的值；左右子树也分别为二叉搜索树。 平衡二叉树：该树所有节点的左右子树的高度相差不超过 1。 示例： 示例 1： 123输入：nums = [-10,-3,0,5,9]输出：[0,-3,9,-10,null,5]解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案： 示例 2： 123输入：nums = [1,3]输出：[3,1]解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。 提示： 1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums 按 严格递增 顺序排列 💡 解题思路 方法一：中序遍历 题目所给的数组其实就是二叉搜索树的中序遍历，我们很容易想到使用二分法 + 递归构建平衡二叉搜索树。 首先使用二分法选择中间...

📝 题目描述 题目链接：二叉树的层序遍历 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。 示例： 示例 1： 12输入：root = [3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]] 示例 2： 12输入：root = [1]输出：[[1]] 示例 3： 12输入：root = []输出：[] 提示： 树中节点数目在范围 [0, 2000] 内 -1000 <= Node.val <= 1000 💡 解题思路 方法一：广度优先搜索 这个题比较简单，我们只需要构造一个队列即可。 首先放入根节点（非空），然后只要队列不为空，我们就持续遍历。 首先获取队列中当前节点的数量，也就是本层的节点数量； 然后进入二层循环，遍历当前节点，存储节点值，并将每个本层节点的非空子节点入队。 当队列为空时，循环结束。 🔧 代码实现 1、广度优先搜索 123456789101112131415161718192021222324252627282930313233/** * Defini...

数组 123vector<int> ret;ret.back(); // 代表最后的一个元素ret[ret.size() - 1]; 堆 12// 最大堆priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pri_que; 12345678910111213141516// 最小堆struct compare { bool operator()(ListNode* a, ListNode* b) { return a -> val > b -> val; }};class Solution {public: ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNod...

📝 题目描述 题目链接：二叉树的直径 给你一棵二叉树的根节点，返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root。 两节点之间路径的 长度 由它们之间边数表示。 示例： 示例 1： 123输入：root = [1,2,3,4,5]输出：3解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。 示例 2： 12输入：root = [1,2]输出：1 提示： 树中节点数目在范围 [1, 10^4] 内 -100 <= Node.val <= 100 💡 解题思路 方法一：深度优先搜索 本质上还是后序遍历的思想。 一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。 求直径−>求节点求直径 -> 求节点 求直径−>求节点 而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。 假设我们知道对于该节点的左儿子向下遍历经过最多的节点数 L （即以左儿子为根的子树的深度）...