力扣爆刷第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);}
}