很多时候不懂事

📝 题目描述 题目链接：将有序数组转换为二叉搜索树 给你一个整数数组 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; 12345678910111213// 最小堆struct compare { bool operator()(ListNode* a, ListNode* b) { return a -> val > b -> val; }};class Solution {public: ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, ve...

📝 题目描述 题目链接：二叉树的直径 给你一棵二叉树的根节点，返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 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 （即以左儿子为根的子树的深度）...

📝 题目描述 题目链接：对称二叉树 给你一个二叉树的根节点 root， 检查它是否轴对称。 示例： 示例 1： 12输入：root = [1,2,2,3,4,4,3]输出：true 示例 2： 12输入：root = [1,2,2,null,3,null,3]输出：false 提示： 树中节点数目在范围 [1, 1000] 内 -100 <= Node.val <= 100 💡 解题思路 方法一：递归 判断一棵树是否对称，本质上是判断它的左子树和右子树是否是相互镜像的。 如果同时满足下面的条件，两个树互为镜像： 它们的两个根结点具有相同的值 每个树的右子树都与另一个树的左子树镜像对称 我们可以实现这样一个递归函数，通过“同步移动”两个指针的方法来遍历这棵树。 首先获取根节点的左节点指针 left 和右节点指针 right，然后进入函数，首先比较这两个指针是否相同，然后left->left和right->right进行比较，left->right和right->left进行比较。即这两个指针移动方向相反，随后 left 左移时，r...

📝 题目描述 题目链接：翻转二叉树 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 示例： 示例 1： 12输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1] 示例 2： 12输入：root = [2,1,3]输出：[2,3,1] 示例 3： 12输入：root = []输出：[] 提示： 树中节点数目范围在 [0, 100] 内 -100 <= Node.val <= 100 💡 解题思路 方法一：递归 深度优先搜索的思想，前序遍历和后序遍历的思想都可以解答这道题。 方法二：迭代 广度优先搜索，也就是层序遍历的思路。 访问每层的各个节点，然后交换其左右子树的指针。 🔧 代码实现 1、递归 123456789101112131415161718192021222324/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode...

📝 题目描述 题目链接：二叉树的最大深度 给定一个二叉树 root ，返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例： 示例 1： 12输入：root = [3,9,20,null,null,15,7]输出：3 示例 2： 12输入：root = [1,null,2]输出：2 提示： 树中节点的数量在 [0, 10^4] 区间内 -100 <= Node.val <= 100 💡 解题思路 方法一：深度优先搜索（递归） 深度优先的思路，如果我们知道了左子树和右子树的最大深度 lll 和 rrr，那么该二叉树的最大深度即为： max(l,r)+1max(l,r) + 1 max(l,r)+1 而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用“深度优先搜索”的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1)O(1)O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。 方法二：广度优先搜索（迭代） 广度...

📝 题目描述 题目链接：二叉树的中序遍历 给定一个二叉树的根节点 root ，返回它的 中序遍历 。 示例： 示例 1： 12输入：root = [1,null,2,3]输出：[1,3,2] 示例 2： 12输入：root = []输出：[] 示例 3： 12输入：root = [1]输出：[1] 提示： 树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100 💡 解题思路 方法一：递归 二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，并且在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。 因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。 方法二：迭代 方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同。 ★方法三：Morris 中序遍历 Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)O(1)O(1)。 M...

📝 题目描述 题目链接：LRU 缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1)O(1)O(1) 的平均时间复杂度运行。 示例： 12345678910111213141516171819输入["LRUCache", "put", "put", "get", "put", "get", ...

📝 题目描述 题目链接：合并 K 个升序链表 给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例： 123456789101112131415161718192021222324示例 1：输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6示例 2：输入：lists = []输出：[]示例 3：输入：lists = [[]]输出：[] 提示： k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] 按 升序 排列 lists[i].length 的总和不超过 10^4 ...