文章目录
🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨
452.【中等】用最少数量的箭引爆气球
题目描述：
- 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
- 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
- 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
- 示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
- 示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
class Solution {
public int findMinArrowShots(int[][] points) {
int n = points.length, ans = 1; // n是气球的数量，ans是箭的数量，初始化为1因为至少需要一支箭
// 按气球的结束位置进行升序排序，以便后续处理公共区间
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] point1, int[] point2) {
// 注意：原代码按结束位置排序的逻辑是反的，这里修正为按结束位置升序排序
if (point1[1] > point2[1]) {
return 1;
} else if (point1[1] < point2[1]) {
return -1;
} else {
return 0;
}
}
});
// 初始化公共区间的左右边界为第一个气球的左右边界
int public_l = points[0][0], public_r = points[0][1];
// 遍历每个气球
for(int[] cur : points){
int cur_l = cur[0], cur_r = cur[1]; // 当前气球的左右边界
// 更新公共区间的左右边界，确保公共区间尽可能大
public_l = Math.max(public_l, cur_l);
public_r = Math.min(public_r, cur_r);
// 如果公共区间不存在（即左边界大于右边界），说明当前箭无法射爆之前的所有气球
// 需要另起一支箭，并更新公共区间的左右边界为当前气球的左右边界
if(public_l > public_r){
ans++; // 箭的数量加1
public_l = cur_l; // 更新公共区间的左边界
public_r = cur_r; // 更新公共区间的右边界
}
}
// 返回箭的总数
return ans;
}
}
236.【中等】二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 如果当前节点是p或q，或者当前节点为空（已经遍历到叶子节点的下一个null），则返回当前节点
if (root == p || root == q || root == null) return root;
// 递归地在左子树中查找p和q的LCA
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 递归地在右子树中查找p和q的LCA
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 如果左子树和右子树中都找到了目标节点（即left和right都不为null），说明当前节点就是LCA
if (left != null && right != null) return root;
// 如果左子树中没有找到目标节点（left为null），则返回右子树中的结果
// 这意味着LCA一定在右子树中，或者就是右子树本身（如果right是p或q）
if (left == null) return right;
// 如果右子树中没有找到目标节点（right为null），则返回左子树中的结果
// 这意味着LCA一定在左子树中，或者就是左子树本身（如果left是p或q）
return left;
}
}
199.【中等】二叉树的右视图
题目描述：
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new ArrayList<>(); // 初始化一个ArrayList来存储结果
if (root == null) return ans; // 如果根节点为空，则直接返回空列表
Queue<TreeNode> q = new LinkedList<>(); // 创建一个队列用于BFS遍历
q.offer(root); // 将根节点加入队列
while (!q.isEmpty()) { // 当队列不为空时，继续遍历
int count = q.size(); // 获取当前层的节点数
for (int i = 0; i < count; i++) { // 遍历当前层的所有节点
TreeNode node = q.poll(); // 从队列中取出一个节点
if (node.left != null) q.offer(node.left); // 如果左子节点不为空，则将其加入队列
if (node.right != null) q.offer(node.right); // 如果右子节点不为空，则将其加入队列
// 当遍历到当前层的最后一个节点时，将其值添加到结果列表中
if (i == count - 1) ans.add(node.val);
}
}
return ans;
}
}
103.【中等】二叉树的锯齿形层序遍历
题目描述：
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
解题思路：
- 我们按层数的奇偶来决定每一层的输出顺序。规定二叉树的根节点为第 0 层，如果当前层数是偶数，从左至右输出当前层的节点值，否则，从右至左输出当前层的节点值。
- 修改广度优先搜索，对树进行逐层遍历，用队列维护当前层的所有元素，当队列不为空的时候，求得当前队列的长度 size，每次从队列中取出 size 个元素进行拓展，然后进行下一次迭代。
- 为了满足题目要求的返回值为「先从左往右，再从右往左」交替输出的锯齿形，我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。
- 双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展，但是对当前层节点的存储我们维护一个变量 isOrderLeft 记录是从左至右还是从右至左的：
- 如果从左至右，我们每次将被遍历到的元素插入至双端队列的末尾。
- 如果从右至左，我们每次将被遍历到的元素插入至双端队列的头部。
当遍历结束的时候我们就得到了答案数组。
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new LinkedList<List<Integer>>(); // 初始化结果列表，用于存储每一层的节点值
if (root == null) {
return ans; // 如果根节点为空，则直接返回空的结果列表
}
Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>(); // 创建一个队列用于层次遍历
nodeQueue.offer(root); // 将根节点加入队列
boolean isOrderLeft = true; // 标记当前层是否从左到右遍历，初始化为true
while (!nodeQueue.isEmpty()) { // 当队列不为空时，继续遍历
Deque<Integer> levelList = new LinkedList<Integer>(); // 创建一个双端队列，用于存储当前层的节点值，方便从两端插入
int size = nodeQueue.size(); // 获取当前层的节点数
for (int i = 0; i < size; ++i) { // 遍历当前层的所有节点
TreeNode curNode = nodeQueue.poll(); // 从队列中取出一个节点
if (isOrderLeft) {
levelList.offerLast(curNode.val); // 如果从左到右遍历，则将节点值从双端队列的右端插入
} else {
levelList.offerFirst(curNode.val); // 如果从右到左遍历，则将节点值从双端队列的左端插入
}
if (curNode.left != null) {
nodeQueue.offer(curNode.left); // 如果左子节点不为空，则将其加入队列
}
if (curNode.right != null) {
nodeQueue.offer(curNode.right); // 如果右子节点不为空，则将其加入队列
}
}
ans.add(new LinkedList<Integer>(levelList)); // 将当前层的节点值列表添加到结果列表中
isOrderLeft = !isOrderLeft; // 切换遍历方向
}
return ans;
}
}
230.【中等】二叉搜索树中第K小的元素
题目描述：
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
class Solution {
int res, k;
void dfs(TreeNode root) {
// 如果当前节点为空，则直接返回
if (root == null) return;
// 先遍历左子树
dfs(root.left);
// 如果k已经减到0，说明已经找到了第k小的元素，但由于是先遍历左子树，
// 这里实际上是找到了第k个被访问的节点，但因为是BST，所以它就是第k小的
// 如果k不等于0，则继续减1，并检查是否减到了0
if (k == 0) return; // 但这行代码在逻辑上其实是多余的，因为下面的if语句会检查k是否为1
// 如果k减到1，则当前节点就是我们要找的第k小的元素
if (--k == 0) res = root.val;
// 最后遍历右子树
dfs(root.right);
}
// 主方法，用于找到二叉搜索树中第k小的元素
public int kthSmallest(TreeNode root, int k) {
// 初始化全局变量k和res
this.k = k;
this.res = 0; // 初始化res为0，虽然对于BST来说这个初始值不重要，但保持好的编程习惯总是好的
// 开始深度优先搜索
dfs(root);
// 返回找到的第k小的元素的值
return res;
}
}
✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊
🏠 我在CSDN等你哦！我的主页😍
