力扣爆刷第161天之TOP100五连刷71-75（搜索二叉树、二维矩阵、路径总和）
文章目录
一、98. 验证二叉搜索树
题目链接：https://leetcode.cn/problems/validate-binary-search-tree/description/
思路：验证二叉搜索树，二叉搜索数要求任意节点大于左孩子，小于右孩子。这么来看二叉搜索树的中序遍历正好是单调递增序列，所以要判断是否是二叉搜索树，只需要使用中序遍历，并且记录前一个节点的值，用来比较即可。
class Solution {
TreeNode pro = null;
boolean flag = true;
public boolean isValidBST(TreeNode root) {
traverse(root);
return flag;
}
void traverse(TreeNode root) {
if(root == null || !flag) return ;
traverse(root.left);
if(pro != null && pro.val >= root.val) {
flag = false;
return;
}
pro = root;
traverse(root.right);
}
}
二、394. 字符串解码
题目链接：https://leetcode.cn/problems/decode-string/description/
思路：类似于拼接字符串，又带有左右括号，一般看到左右括号类型的题目都要考虑一下，能不能使用栈来做，因为一般左右匹配都是使用栈。本题仔细思考可以发现确实是的，类似于计算表达式，使用两个栈，一个是数字栈，一个是字符串栈，每次遇到左括号就把收集到的字符串和数字压栈，然后启用一个新的字符串和数字记录最新的左括号内的内容，直到遇到右括号，就可以根据数字栈内的内容复制次数，然后拼接字符串栈栈顶元素，以此往复即可。
class Solution {
public String decodeString(String s) {
LinkedList<Integer> stk1 = new LinkedList<>();
LinkedList<String> stk2 = new LinkedList<>();
StringBuilder res = new StringBuilder();
int num = 0;
for(char c : s.toCharArray()) {
if(c >= '0' && c <= '9') {
num = num * 10 + Integer.parseInt(c + "");
}else if(c == '[') {
stk1.push(num);
num = 0;
stk2.push(res.toString());
res = new StringBuilder();
}else if(c == ']') {
StringBuilder t = new StringBuilder();
int count = stk1.pop();
for(int i = 0; i < count; i++) {
t.append(res);
}
res = new StringBuilder(stk2.pop() + t);
}else{
res.append(c);
}
}
return res.toString();
}
}
三、34. 在排序数组中查找元素的第一个和最后一个位置
题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
思路：求排序数组中目标元素出现的最左位置和最右位置，其实就是采用二分查找，分开查找，先查找左边界再查找右边界。然后注意边界条件，即元素是否存在，查出来的边是否超界。
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = findLeft(nums, target);
int right = findRight(nums, target);
return new int[]{left, right};
}
int findLeft(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] >= target) {
right = mid-1;
}else{
left = mid+1;
}
}
if(left < 0 || left >= nums.length) return -1;
return nums[left] == target ? left : -1;
}
int findRight(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] <= target) {
left = mid + 1;
}else{
right = mid - 1;
}
}
if(right < 0 || right >= nums.length) return -1;
return nums[right] == target ? right : -1;
}
}
四、113. 路径总和 II
题目链接：https://leetcode.cn/problems/path-sum-ii/description/
思路：求和满足目标的路径，相当于在二叉树上做回溯，从上往下进行搜索，本质还是回溯，只需要把前序位置收集，在后序位置丢弃，对应了回溯的开始与结束，后序位置表示左右子树都遍历完了要返回上一级，自然需要删除收集的元素完成回溯。
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int sum = 0;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
backTracking(root, targetSum);
return result;
}
void backTracking(TreeNode root, int targetSum) {
if(root == null) return;
sum += root.val;
list.add(root.val);
if(root.left == null && root.right == null && sum == targetSum) {
result.add(new ArrayList(list));
}
backTracking(root.left, targetSum);
backTracking(root.right, targetSum);
list.remove(list.size()-1);
sum -= root.val;
}
}
五、240. 搜索二维矩阵 II
题目链接：https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
思路：搜索二维矩阵，这个二维矩阵有一个特点，就是从左往右是递增的，从上往下是递增，那么也就在右上角构成了一个分界线，可以从这个位置开始深度优先搜索，如果当前元素小于目标元素，那就向下搜索，如果当前元素大于目标元素，那就是向左搜索。
class Solution {
boolean flag = false;
public boolean searchMatrix(int[][] matrix, int target) {
dfs(matrix, target, 0, matrix[0].length-1);
return flag;
}
void dfs(int[][] matrix, int target, int x, int y) {
if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) return;
if(matrix[x][y] == target) {
flag = true;
return;
}else if(matrix[x][y] > target) dfs(matrix, target, x, y-1);
else dfs(matrix, target, x+1, y);
}
}
