力扣爆刷第116天之CodeTop100五连刷66-70

力扣爆刷第116天之CodeTop100五连刷66-70

一、144. 二叉树的前序遍历

题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
思路：前序遍历什么可以说的，在进入左右子树前收集节点。

class Solution {List<Integer> list = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {if(root == null) return list;list.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return list;}
}

二、543. 二叉树的直径

题目链接：https://leetcode.cn/problems/diameter-of-binary-tree/description/
思路：求直径其实就是求某个节点的左子树深度与右子树深度，连接成的一个向上的尖括号，理解了这个关系，就直接像求深度一样，后序遍历，求左右子树深度，记录最大值即可。

class Solution {int max = -1;public int diameterOfBinaryTree(TreeNode root) {traverse(root);return max;}int traverse(TreeNode root) {if(root == null) return 0;int left = traverse(root.left);int right = traverse(root.right);max = Math.max(max, left + right);return Math.max(left, right) + 1;}
}

三、98. 验证二叉搜索树

题目链接：https://leetcode.cn/problems/validate-binary-search-tree/description/
思路：直接中序遍历，用一个变量记录前一个节点，然后中序遍历比较，如果不是，直接早停返回。

class Solution {boolean flag = true;TreeNode pro = null;public boolean isValidBST(TreeNode root) {traverse(root);return flag;}void traverse(TreeNode root) {if(root == null || !flag) return;traverse(root.left);if(pro != null) {if(pro.val >= root.val) {flag = false;return;} }pro = root;traverse(root.right);}
}

四、470. 用 Rand7() 实现 Rand10()

题目链接：https://leetcode.cn/problems/implement-rand10-using-rand7/description/
思路：可以采用概率组合，我们可以先用rand7构造出来一个p=0.2，再构造出来一个p=0.5，这两个事件构成一个事件的概率为p=0.1正好可以达到要求，例如先随机出来一个1-6的数，奇数偶数出现的概率为0.5，范围只要是偶数就行，然后我们再随机出来一个1-5的数，因为我们只放出来1-5，就相当于袋子里只有5个数，那每种数出现的概率就为0.2，然后组合到一块，判断第一个数是奇数还是偶数，通过这个返回1-5或者6-10。就相当于0.5*0.2；

class Solution extends SolBase {public int rand10() {int first, second;while((first = rand7()) > 6) ;while((second = rand7()) > 5) ;return (first & 1) == 1 ? second : 5 + second;}
}

五、64. 最小路径和

题目链接：https://leetcode.cn/problems/minimum-path-sum/description/
思路：定义dp[i][j]表示抵达grid[i][j]时的最短路径，由于只能从上和左的方向推出，则dp[i][j]=grid[i][j]+dp[i-1][j-1]，如果要压缩到一维，也是可以的，注意初始化。

class Solution {public int minPathSum(int[][] grid) {int m = grid.length, n = grid[0].length;int[] dp = new int[n+1];Arrays.fill(dp, Integer.MAX_VALUE);for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {int t = Math.min(dp[j+1], dp[j]);t = t == Integer.MAX_VALUE ? 0 : t;dp[j+1] = grid[i][j] + t;}}return dp[n];}
}